QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#497966 | #5073. Elden Ring | PorNPtree | WA | 172ms | 10668kb | C++17 | 2.3kb | 2024-07-29 21:04:07 | 2024-07-29 21:04:09 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
vector<int> G[N];
int a[N], d[N], vis[N];
signed main() {
int T; scanf("%d", &T);
while (T--) {
int n, m, A, B; scanf("%d%d%d%d", &n, &m, &A, &B);
for (int i = 1; i <= n; ++i) G[i].clear();
for (int i = 1, x, y; i <= m; ++i) {
scanf("%d%d", &x, &y);
G[x].push_back(y), G[y].push_back(x);
}
for (int i = 1; i <= n; ++i) scanf("%d", &a[i]), ((i > 1) && (a[i] += B));
A -= B;
if (A <= 0) {
for (int i = 1; i <= n; ++i) d[i] = 1e9;
d[1] = 0;
queue<int> Q; Q.push(1);
while (!Q.empty()) {
int x = Q.front();
Q.pop();
for (auto v : G[x]) {
if (d[x] + 1 < d[v] && a[1] + d[x] * A > a[v]) {
d[v] = d[x] + 1, Q.push(v);
}
}
}
printf("%d\n", d[n] > 1e8 ? -1 : d[n]);
} else {
for (int i = 1; i <= n; ++i) vis[i] = 0;
priority_queue< pair<int, int>, vector< pair<int, int> >, greater< pair<int, int> > > pq;
int t = 0;
for (auto x : G[1]) pq.push(make_pair(a[x], x)), vis[x] = 1;
while (!pq.empty()) {
int x = pq.top().second; pq.pop();
if (a[1] + t <= a[x]) break;
++t;
for (auto v : G[x]) if (!vis[v]) pq.push(make_pair(a[v], v)), vis[v] = 1;
}
while (!pq.empty()) pq.pop();
for (int i = 1; i <= n; ++i) d[i] = 1e9;
pq.push(make_pair(d[1] = 0, 1));
while (!pq.empty()) {
int x = pq.top().second;
if (pq.top().first != d[x]) {
pq.pop();
continue;
}
pq.pop();
for (auto v : G[x]) {
if (max(d[x], (a[1] + d[x] * A > a[v] ? 0 : (a[v] - a[1] + A) / A)) + 1 < d[v]) {
d[v] = max(d[x], (a[1] + d[x] * A > a[v] ? 0 : (a[v] - a[1] + A) / A)) + 1;
pq.push(make_pair(d[v], v));
}
}
}
printf("%d\n", d[n] > t ? -1 : d[n]);
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 10668kb
input:
2 5 4 5 8 1 2 1 3 1 4 4 5 15 1 1 1 1 5 4 10 5 1 2 1 3 1 4 4 5 10 4 4 4 19
output:
2 4
result:
ok 2 number(s): "2 4"
Test #2:
score: -100
Wrong Answer
time: 172ms
memory: 10240kb
input:
100000 6 10 107812 105568 6 5 3 6 4 6 4 2 5 1 5 6 4 5 1 3 1 2 2 5 124065 140875 29890 80077 116532 35394 9 10 82107 88302 1 2 2 3 5 3 5 1 1 4 9 6 3 5 8 2 5 6 7 5 22670 3735 33660 92823 139960 89319 83335 158330 117349 6 10 181257 173221 5 3 3 4 3 1 5 1 2 1 3 6 3 1 6 2 3 6 4 3 76902 46253 123092 2661...
output:
-1 -1 -1 1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 3 -1 2 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 2 -1 -1 -1 -1 -1 ...
result:
wrong answer 133rd numbers differ - expected: '8', found: '-1'