結果
問題 |
No.2712 Play more!
|
ユーザー |
|
提出日時 | 2024-03-31 14:39:10 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,253 bytes |
コンパイル時間 | 3,102 ms |
コンパイル使用メモリ | 253,908 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-09-30 19:47:39 |
合計ジャッジ時間 | 4,693 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 31 WA * 2 |
ソースコード
#include<bits/stdc++.h> using namespace std; #define rep(i,n) for(int i = 0;i < n;i++) template<class T> bool chmin(T &a,T b){ if(a>b){a = b;return true;} return false; } template<class T> bool chmax(T &a,T b){ if(a<b){a = b;return true;} return false; } using ll = long long; using ld = long double; // const int INF = 1e9+5; // const int mod = 1000000007; const int mod = 998244353; void no(){ cout << "No" << endl;exit(0); } void yes(){ cout << "Yes" << endl; exit(0); } #define all(x) x.begin(),x.end() #include<bits/stdc++.h> using namespace std; using ll = long long; const ll INF = 1LL<<60; struct Edge{ int to; ll w;//cost Edge(int to, ll w):to(to),w(w){}//コンストラクタ 頂点番号、コスト }; using Graph = vector<vector<Edge>>; //負の閉路があるかどうかと、ない場合はvectorを返す pair<bool,vector<ll>> BellmanFord(Graph &G, int s){ int N = (int)G.size(); bool exist_negative_cycle = false;//一旦負の閉路がないことに vector<ll>dist(N,INF); dist[s]=0; for(int i = 0;i < N;i++){//頂点数だけ緩和をする bool update = false;//更新が発生したかどうか for(int v = 0;v < N;v++){ if(dist[v]==INF)continue;//まだ見なくていい for(auto e:G[v]){ if(chmin(dist[e.to],dist[v]+e.w)){ update = true; } } } if(!update)break;//既に最短経路長が求まってる if(i==N-1&&update)exist_negative_cycle = true;//負の閉路がある場合 } return pair<bool,vector<ll>>(exist_negative_cycle,dist); } int main(){ #define int long long //移動時間-攻略時間を最小に int N,M;cin >> N >> M; vector<int>A(N);//攻略時間 rep(i,N)cin >> A[i]; Graph G(N); //頂点0の攻略は最後に考慮すればよい rep(i,M){ int a,b,c;cin >> a >> b >> c; //移動と、行先の攻略時間 a--;b--; G[a].emplace_back(b,c-A[b]);//移動-頂点bの攻略 } auto [f,d] = BellmanFord(G,0); if(f){ cout << "inf" << endl;return 0; } int res = d[N-1]; cout << (res-A[0])*-1LL << endl; }