QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#466284#6523. Escape PlanNGDtuanhWA 420ms51744kbC++171.5kb2024-07-07 17:32:062024-07-07 17:32:07

Judging History

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

  • [2024-07-07 17:32:07]
  • 评测
  • 测评结果:WA
  • 用时:420ms
  • 内存:51744kb
  • [2024-07-07 17:32:06]
  • 提交

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

詳細信息

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'