QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#284083 | #5458. Shortest Path Query | bobbilyking | 0 | 0ms | 7032kb | C++17 | 2.2kb | 2023-12-16 04:09:47 | 2023-12-16 04:09:47 |
Judging History
你现在查看的是测评时间为 2023-12-16 04:09:47 的历史记录
- [2024-06-21 12:38:30]
- 管理员手动重测本题所有提交记录
- 测评结果:Compile Error
- 用时:0ms
- 内存:0kb
- [2023-12-16 04:09:47]
- 提交
answer
#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include<bits/stdc++.h>
#include<math.h>
using namespace std;
typedef int ll;
typedef long double ld;
typedef pair<ll, ll> pl;
typedef vector<ll> vl;
#define FD(i, r, l) for(ll i = r; i > (l); --i)
#define K first
#define V second
#define G(x) ll x; cin >> x;
#define GD(x) ld x; cin >> x;
#define GS(s) string s; cin >> s;
#define EX(x) { cout << x << '\n'; exit(0); }
#define A(a) (a).begin(), (a).end()
#define F(i, l, r) for (ll i = l; i < (r); ++i)
#define NN 50010
#define M 1000000007 // 998244353
vector<pl> opt[NN];
ll indeg[NN];
vector<pl> adj[NN];
vl optVec[NN]; // convert to opt later
int main(){
// freopen("a.in", "r", stdin);
// freopen("a.out", "w", stdout);
ios_base::sync_with_stdio(false); cin.tie(0);
cout << fixed << setprecision(20);
G(n) G(m) while(m--) {
G(u) G(v) G(c)
adj[u].emplace_back(v,c);
indeg[v]++;
}
F(i, 1, n+1) optVec[i].assign(n+1, n+1);
optVec[1][0] = 0;
{
vector<ll> q{1}, nq;
for (; q.size(); swap(q, nq), nq.clear()) {
for (auto i: q) {
for (auto [x, w]: adj[i]) {
F(white, 0, n) optVec[x][white + (w == 0)] = min(optVec[x][white + (w == 0)], optVec[i][white] + (w == 1));
// idk if this is needed or some more sophisticated merging is needed or some dumb merging is fine
if (!--indeg[x]) nq.push_back(x);
}
}
}
}
F(cur, 1, n+1) {
// compute pareto front (should probably reason about this, i ahve shit intuition)
FD(x, optVec[cur].size()-1, -1) {
ll y = -optVec[cur][x];
while (opt[cur].size() and y >= opt[cur].back().V) opt[cur].pop_back();
opt[cur].emplace_back(x, y);
}
for (auto &[x, y]: opt[cur]) y=-y;
}
// Fe
G(q) while(q--){
G(a) G(b) G(t)
ll ans = INT_MAX;
for (auto [x, y]: opt[t]) ans = min(ans, x*a + y*b);
cout << ans << '\n';
}
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 7032kb
input:
4 4 1 2 0 1 3 1 2 4 0 3 4 1 3 3 5 2 3 2 4 2 3 4
output:
3 4 4
result:
ok 3 number(s): "3 4 4"
Test #2:
score: -100
Time Limit Exceeded
input:
50000 100000 1 2 1 2 3 0 3 4 1 4 5 0 5 6 1 6 7 0 7 8 1 8 9 1 9 10 0 10 11 1 11 12 1 12 13 1 13 14 0 14 15 0 15 16 0 16 17 0 17 18 1 18 19 1 19 20 0 20 21 1 21 22 0 22 23 0 23 24 1 24 25 1 25 26 0 26 27 1 27 28 0 28 29 0 29 30 0 30 31 0 31 32 1 32 33 0 33 34 1 34 35 1 35 36 1 36 37 1 37 38 0 38 39 0 ...