QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#664958#5579. Bog of Eternal Stenchenze114514WA 1ms3964kbC++201.6kb2024-10-21 23:50:062024-10-21 23:50:07

Judging History

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

  • [2024-10-21 23:50:07]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3964kb
  • [2024-10-21 23:50:06]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;

#define pb push_back

const ld pi = 3.14159265358979323846;
const ll INF = 1e18;
const int mod = (int)1e9 + 7;

template<typename T>
T chmax(T a, T b) {
    return a > b ? a : b;
}

template<typename T>
T chmin(T a, T b) {
    return a > b ? b : a;
}

const int N = 3e3 + 1, M = N * 2;


void solve() {
     int n, m;
    cin >> n >> m;
    const ll INF = 1e18;
    vector<vector<pair<int, ll>>> adj(n + 1);

    for (int i = 0; i < m; ++i) {
        int u, v;
        ll w;
        cin >> u >> v >> w;
        adj[u].emplace_back(v, w);
    }

    vector<ll> f(n + 1, INF);
    vector<int> vs(n + 1, 0);
  
    f[1] = 0;
    priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<>> q;

    q.push({0, 1});

    while (!q.empty()) {
        auto p = q.top();
        q.pop();

        int u = p.second;
        if(vs[u] > n){
            continue;
        }
        vs[u]++;

        for(auto g : adj[u]){
            int v = g.first, w = g.second;
            if(f[v] > chmax(0ll, f[u] + w)){
                if(vs[v]){
                    f[v] = (w < 0 ? 0 : chmax(0ll, f[u] + w));
                }
                else{
                    f[v] = chmax(0ll, f[u] + w);
                }
                q.push({f[v], v});
            }
        }
    }

    cout << f[n] << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int t = 1;
    // cin >> t;

    while (t--) {
        solve();
    }

    return 0;
}

详细

Test #1:

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

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: 1ms
memory: 3612kb

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: 1ms
memory: 3812kb

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: 1ms
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: 3484kb

input:

2 1
1 2 0

output:

0

result:

ok single line: '0'

Test #6:

score: 0
Accepted
time: 1ms
memory: 3780kb

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: 0
Accepted
time: 1ms
memory: 3620kb

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:

2

result:

ok single line: '2'

Test #8:

score: 0
Accepted
time: 1ms
memory: 3608kb

input:

46 1981
29 18 47
29 4 71
17 44 26
42 10 50
26 5 13
12 31 41
18 4 57
27 34 83
5 35 76
29 9 0
29 27 21
25 19 2
10 12 99
39 23 47
41 21 91
46 45 67
34 10 75
29 8 86
16 30 58
18 19 4
37 38 70
37 18 -3
11 27 -2
40 31 84
28 44 88
6 19 84
14 26 12
40 17 52
24 5 95
33 35 63
10 2 60
22 35 67
14 18 17
45 28 1...

output:

7

result:

ok single line: '7'

Test #9:

score: -100
Wrong Answer
time: 0ms
memory: 3864kb

input:

46 1981
29 18 10
29 4 47
17 44 43
42 10 6
26 5 27
12 31 13
18 4 25
27 34 14
5 35 72
29 9 55
29 27 87
25 19 72
10 12 21
39 23 8
41 21 20
46 45 40
34 10 63
29 8 64
16 30 72
18 19 63
37 38 35
37 18 1
11 27 95
40 31 47
28 44 41
6 19 12
14 26 11
40 17 21
24 5 60
33 35 91
10 2 13
22 35 34
14 18 14
45 28 6...

output:

3

result:

wrong answer 1st lines differ - expected: '1000000001', found: '3'