QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#420894#6523. Escape PlanshepherdWA 2242ms71536kbC++202.1kb2024-05-25 02:57:532024-05-25 02:57:53

Judging History

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

  • [2024-05-25 02:57:53]
  • 评测
  • 测评结果:WA
  • 用时:2242ms
  • 内存:71536kb
  • [2024-05-25 02:57:53]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

static constexpr const ll inf = 1e15;

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n,m,k;
        cin >> n >> m >> k;
        vector<bool> is_exit(n);
        for (int i = 0; i<k; i++) {
            int e;
            cin >> e;
            is_exit[--e] = true;
        }
        vector<int> d(n);
        for (int i = 0; i<n; i++) {
            cin >> d[i];
        }
        vector<vector<pair<int,ll>>> graph(n);
        for (int i = 0; i<m; i++) {
            int x,y;
            ll w;
            cin >> x >> y >> w;
            graph[--x].emplace_back(--y, w);
            graph[y].emplace_back(x, w);
        }
        vector<ll> ret(n, inf);
        vector<bool> marked(n, false);
        vector<multiset<ll>> dd(n);
        auto cmp = [&](int x, int y) {
            auto dx = *prev(end(dd[x]));
            auto dy = *prev(end(dd[y]));
            if (dx != dy) return dx < dy;
            return x < y;
        };
        set<int, decltype(cmp)> q(cmp);
        for (int i = 0; i<n; i++) {
            if (is_exit[i]) {
                dd[i].insert(0);
                q.insert(i);
            }
        }
        while (!q.empty()) {
            auto curr = *q.begin();
            q.erase(q.begin());
            marked[curr] = true;
            ret[curr] = *prev(end(dd[curr]));
            for (const auto& [neighbor, weight] : graph[curr]) {
                if (marked[neighbor]) continue;
                if (int(dd[neighbor].size()) > d[neighbor]) {
                    q.erase(neighbor);
                }
                dd[neighbor].insert(ret[curr] + weight);
                if (int(dd[neighbor].size()) > d[neighbor] + 1) {
                    dd[neighbor].erase(prev(end(dd[neighbor])));
                }
                if (int(dd[neighbor].size()) > d[neighbor]) {
                    q.insert(neighbor);
                }
            }
        }
        if (ret[0] >= inf) cout << -1 << '\n';
        else cout << ret[0] << '\n';
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3512kb

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: 2242ms
memory: 71536kb

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:

5109
2754
3293
4646
3796
3394
2783
6772
3095
2492
3296
3521
865
4249
2241
3792
2135
2544
3343
1775
10700
4677
2133
2150
8620
14141
4785
2322
1318
1980
3067
1635
1702
-1
2879
6265
2438
2810
2289
3001
402
3769
18118
6874
7879
3823
-1
510
3623
10564
-1
3166
4107
7526
5549
1959
3302
270
4474
1998
3350
4...

result:

wrong answer 2nd numbers differ - expected: '1021', found: '2754'