QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#690851#5579. Bog of Eternal Stenchohiostatescarlet#WA 8ms3648kbC++171.1kb2024-10-31 05:50:202024-10-31 05:50:21

Judging History

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

  • [2024-10-31 05:50:21]
  • 评测
  • 测评结果:WA
  • 用时:8ms
  • 内存:3648kb
  • [2024-10-31 05:50:20]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);
    int n, m;
    cin >> n >> m;
    vector<array<ll, 3>> edges(m);
    for (int i = 0; i < m; i++) {
        cin >> edges[i][0] >> edges[i][1] >> edges[i][2];
        edges[i][0]--, edges[i][1]--;
    }
    vector<ll> cost(n, 1e18);
    cost[0] = 0;
    for (auto [a, b, w] : edges) {
        for (int i = 0; i < n; i++) {
            cost[b] = min(cost[b], max<ll>(0, cost[a] + w));
        }
    }
    vector<ll> newcost = cost;
    for (auto [a, b, w] : edges) {
        if (cost[a] + w < cost[b]) {
            newcost[b] = 0;
        }
    }
    for (auto [a, b, w] : edges) {
        for (int i = 0; i < n; i++) {
            newcost[b] = min(newcost[b], max<ll>(0, newcost[a] + w));
        }
    }
    cout << newcost[n - 1] << '\n';
}

详细

Test #1:

score: 100
Accepted
time: 8ms
memory: 3572kb

input:

1999 1999
1 2 1000000000
2 3 1000000000
3 4 1000000000
4 5 1000000000
5 6 1000000000
6 7 1000000000
7 8 1000000000
8 9 1000000000
9 10 1000000000
10 11 1000000000
11 12 1000000000
12 13 1000000000
13 14 1000000000
14 15 1000000000
15 16 1000000000
16 17 1000000000
17 18 1000000000
18 19 1000000000
1...

output:

3

result:

ok single line: '3'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3648kb

input:

4 4
1 2 5
1 3 -2
2 4 1
3 4 10

output:

6

result:

ok single line: '6'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3612kb

input:

5 5
1 2 1000
2 3 -3
3 4 1
4 2 0
2 5 2

output:

3

result:

ok single line: '3'

Test #4:

score: 0
Accepted
time: 0ms
memory: 3616kb

input:

3 3
1 3 -10
3 2 2
2 3 -1

output:

0

result:

ok single line: '0'

Test #5:

score: 0
Accepted
time: 0ms
memory: 3496kb

input:

2 1
1 2 0

output:

0

result:

ok single line: '0'

Test #6:

score: 0
Accepted
time: 0ms
memory: 3612kb

input:

6 6
1 2 1000000000
2 6 -1
3 2 0
4 3 -1
3 5 -1
5 4 -1

output:

999999999

result:

ok single line: '999999999'

Test #7:

score: -100
Wrong Answer
time: 1ms
memory: 3592kb

input:

46 1981
29 18 40
29 4 44
17 44 65
42 10 99
26 5 95
12 31 -3
18 4 100
27 34 69
5 35 22
29 9 -5
29 27 16
25 19 4
10 12 75
39 23 83
41 21 51
46 45 35
34 10 4
29 8 30
16 30 82
18 19 62
37 38 8
37 18 9
11 27 68
40 31 71
28 44 90
6 19 70
14 26 64
40 17 87
24 5 91
33 35 -1
10 2 23
22 35 17
14 18 31
45 28 7...

output:

0

result:

wrong answer 1st lines differ - expected: '2', found: '0'