QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#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

你现在查看的是最新测评结果

[2024-07-29 21:04:09]
评测

测评结果：WA
用时：172ms
内存：10668kb

查看

[2024-07-29 21:04:07]
提交

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;
}

源文件, 语言: C++17

详细

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'