結果
問題 |
No.2712 Play more!
|
ユーザー |
|
提出日時 | 2024-03-31 15:24:04 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 70 ms / 2,000 ms |
コード長 | 2,833 bytes |
コンパイル時間 | 3,024 ms |
コンパイル使用メモリ | 267,204 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-09-30 23:50:15 |
合計ジャッジ時間 | 4,343 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 33 |
ソースコード
#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 = LLONG_MAX/3; struct Edge{ int to; ll w;//cost Edge(int to, ll w):to(to),w(w){}//コンストラクタ 頂点番号、コスト }; using Graph = vector<vector<Edge>>; vector<bool>can_go; //負の閉路があるかどうかと、ない場合は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++){//頂点数だけ緩和をする if(can_go[i]==false)continue; bool update = false;//更新が発生したかどうか for(int v = 0;v < N;v++){ if(can_go[v]==false)continue; 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; can_go.resize(N,false);//iからN-1に到達できないなら、除外 vector<int>A(N);//攻略時間 rep(i,N)cin >> A[i]; Graph G(N); vector<vector<int>>rg(N); //頂点0の攻略は最後に考慮すればよい rep(i,M){ int a,b,c;cin >> a >> b >> c; //移動と、行先の攻略時間 a--;b--; G[a].emplace_back(b,c-A[a]);//移動-頂点bの攻略 rg[b].push_back(a); } queue<int>que; can_go[N-1] = true; que.push(N-1); while(!que.empty()){ int q = que.front();que.pop(); for(auto p:rg[q]){ if(can_go[p])continue; can_go[p] = true; que.push(p); } } // for(auto p:can_go)cout << p << ' '; // cout << endl; auto [f,d] = BellmanFord(G,0); if(f){ cout << "inf" << endl;return 0; } int res = d[N-1]; cout << (res-A[N-1])*-1LL << endl; }