結果
問題 | No.2712 Play more! |
ユーザー |
|
提出日時 | 2024-03-31 16:26:44 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,188 bytes |
コンパイル時間 | 2,199 ms |
コンパイル使用メモリ | 207,208 KB |
最終ジャッジ日時 | 2025-02-20 18:06:03 |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 31 WA * 2 |
ソースコード
#include <bits/stdc++.h> using namespace std; int main() { int N,M; cin >> N >> M; vector<int> A(N); for(auto &a : A) cin >> a; vector<vector<pair<int,long long>>> Graph(N); for(int i=0; i<M; i++){ int a,b,c; cin >> a >> b >> c; a--; b--; c = A.at(a)-c; Graph.at(a).push_back({b,c}); } vector<long long> dist(N,-1e18); dist.at(0) = 0; for(int t=0; t<=N; t++){ for(int i=0; i<N; i++){ for(auto [to,c] : Graph.at(i)) dist.at(to) = max(dist.at(to),dist.at(i)+c); } } queue<int> Q; long long inf = 2e18; for(int i=0; i<N; i++){ for(auto [to,c] : Graph.at(i)){ if(dist.at(to) < dist.at(i)+c){ dist.at(to) = inf; cout << "inf" << endl; return 0; Q.push(to); } } } while(Q.size()){ int pos = Q.front(); Q.pop(); for(auto [to,ig] : Graph.at(pos)){ if(dist.at(to) == inf) continue; dist.at(to) = inf; Q.push(to); } } if(dist.at(N-1) == inf) cout << "inf" << endl; else cout << dist.at(N-1)+A.at(N-1) << endl; }