QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#466284 | #6523. Escape Plan | NGDtuanh | WA | 420ms | 51744kb | C++17 | 1.5kb | 2024-07-07 17:32:06 | 2024-07-07 17:32:07 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define For(i, a, b) for (int i = a; i <= b; ++i)
#define RFor(i, a, b) for (int i = a; i >= b; --i)
#define get_bit(bit, mask) (((mask) >> (bit)) & 1)
#define set_bit(bit, mask) (mask |= (1ll << bit))
#define top_bit(mask) (31 - __builtin_clz(mask))
#define log(a) cout << #a << " = " << a << '\n'
#define ii pair<int, int>
#define iii tuple<int, int, int>
const int N = 1e5 + 5;
const int INF = 2e18 + 5;
int ans;
int n, m, k;
int e[N], d[N];
vector<ii> adj[N];
int dis[N];
void GetInput() {
cin >> n >> m >> k;
For(i, 1, k) cin >> e[i];
For(i, 1, n) cin >> d[i];
int x, y, w;
fill(adj, adj + n + 1, vector<ii>());
For(i, 1, m)
cin >> x >> y >> w,
adj[y].push_back({ x, w });
}
void Rep() {
cout << ans << '\n';
}
void Solve() {
fill(dis, dis + n + 1, INF);
priority_queue<ii, vector<ii>, greater<ii>> que;
For(i, 1, k)
d[e[i]] = 0,
que.push({ 0, e[i] });
while (que.size()) {
auto [len, node] = que.top(); que.pop();
// cout << node << ": " << d[node] << '\n';
if (d[node]-- != 0) continue;
dis[node] = len;
for (auto [child, del] : adj[node])
que.push({ len + del, child });
}
ans = dis[1] == INF ? -1 : dis[1];
}
signed main() {
#ifndef LOCAL
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#endif
int t; cin >> t;
while (t--)
GetInput(),
Solve(),
Rep();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 7680kb
input:
2 3 4 1 3 1 1 1 1 2 1 1 2 2 2 3 1 2 3 2 3 2 2 2 3 2 0 0 1 2 1 1 3 1
output:
4 -1
result:
ok 2 number(s): "4 -1"
Test #2:
score: -100
Wrong Answer
time: 420ms
memory: 51744kb
input:
100 100 1808 2 94 47 3 3 0 2 4 3 3 4 0 0 2 2 2 3 2 4 0 2 3 4 4 2 0 3 4 3 1 0 2 1 2 2 0 3 4 4 4 1 2 2 3 1 0 0 3 1 4 2 1 3 3 4 3 0 4 1 0 3 2 1 4 4 1 3 2 3 3 3 3 1 0 3 0 4 3 1 0 4 0 4 4 1 2 0 0 4 1 3 3 3 0 2 2 1 1 2 3 4 1 2 72 29 1138 59 78 2398 95 5 1610 32 46 4176 36 99 8143 100 69 413 61 58 1595 9 9...
output:
10066 1021 7388 7333 4908 6137 4117 12073 4997 4794 6709 4292 1428 9305 3542 12486 6617 5093 7707 3731 13199 13114 3205 8924 15860 18912 6228 15275 1318 4526 6087 3304 2735 -1 12842 6265 3755 5442 3917 5894 402 13640 -1 10931 11053 7105 -1 986 3623 27647 -1 3166 5970 15924 10732 2303 6451 270 7188 2...
result:
wrong answer 1st numbers differ - expected: '5109', found: '10066'