QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#664954#5579. Bog of Eternal Stenchenze114514TL 0ms0kbC++201.5kb2024-10-21 23:49:112024-10-21 23:49:12

Judging History

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

  • [2024-10-21 23:49:12]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [2024-10-21 23:49:11]
  • 提交

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;

        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: 0
Time Limit Exceeded

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:


result: