QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#664932#5579. Bog of Eternal Stenchenze114514WA 1ms3616kbC++201.5kb2024-10-21 23:37:292024-10-21 23:37:30

Judging History

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

  • [2024-10-21 23:37:30]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3616kb
  • [2024-10-21 23:37:29]
  • 提交

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] > 1){
            continue;
        }
        vs[u]++;

        for(auto g : adj[u]){
            int v = g.first, w = g.second;
            if(f[v] > f[u] + w){
                f[v] = (w < 0 ? 0 : 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: 3616kb

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: 3596kb

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: 3592kb

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: 3524kb

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: 3544kb

input:

2 1
1 2 0

output:

0

result:

ok single line: '0'

Test #6:

score: -100
Wrong Answer
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:

0

result:

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