結果
問題 |
No.2712 Play more!
|
ユーザー |
![]() |
提出日時 | 2024-03-31 14:38:45 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 70 ms / 2,000 ms |
コード長 | 2,269 bytes |
コンパイル時間 | 1,591 ms |
コンパイル使用メモリ | 171,280 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-09-30 23:47:35 |
合計ジャッジ時間 | 2,688 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 33 |
ソースコード
#include <bits/stdc++.h> using ll=long long; const long long INF=1LL<<60; struct Edge { int from; int to; long long cost; }; // 頂点Nにつながる負の閉路が存在する場合trueを返す bool BellmanFord(const std::vector<Edge>& edges,std::vector<long long>& distances) { for(size_t i=0;i<distances.size();++i) { bool changed=false; //全ての辺の操作 for(const auto& edge:edges){ // (INF+cost)はINFなので処理しない if(distances[edge.from]==INF){ continue; } const long long d = distances[edge.from]+edge.cost; if(d<distances[edge.to]){ distances[edge.to]=d; changed=true; } } if(!changed){ return false; } } //この検証フェーズなしだと負の閉路のあるなしを検出 //あればゴール地点が負の閉路に繋がっているかを検出 //検証フェーズ //負の閉路からつながる頂点を全て-INFにする for(size_t i=0;i<distances.size();i++){ for(const auto& edge:edges){ // (INF+cost)はINFなので処理しない if(distances[edge.from]==INF){ continue; } const long long d = distances[edge.from]+edge.cost; if(d<distances[edge.to]){ distances[edge.to]=-INF; } } } //検証フェーズ終わり //頂点回数分だけループしても定まらないのは、負の閉路が存在するから if(distances.back()==-INF){ return true; } return false; } int main(){ ll n,m; std::cin >> n >> m; std::vector<ll>A(n); for(auto&a:A)std::cin >> a; std::vector<Edge>edges(m); for(auto&edge:edges){ std::cin >> edge.from >> edge.to >> edge.cost; --edge.from;--edge.to; edge.cost-=A[edge.to]; } std::vector<ll>distances(n,INF); distances[0]=-A[0]; if(BellmanFord(edges, distances)){ std::cout << "inf\n"; } else{ std::cout << -distances.back() << '\n'; } }