結果
問題 |
No.2712 Play more!
|
ユーザー |
|
提出日時 | 2024-03-31 15:27:53 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 61 ms / 2,000 ms |
コード長 | 1,784 bytes |
コンパイル時間 | 2,579 ms |
コンパイル使用メモリ | 211,048 KB |
最終ジャッジ日時 | 2025-02-20 17:55:09 |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 33 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll=long long; using ld=long double; template<class T> using graph=vector<vector<T>>; template<class T> using min_priority_queue=priority_queue<T,vector<T>,greater<T>>; constexpr int INF32=INT_MAX/2; constexpr ll INF64=1LL<<60; constexpr array<int,4> DX4={0,1,0,-1}; constexpr array<int,4> DY4={-1,0,1,0}; constexpr array<int,8> DX8={0,1,1,1,0,-1,-1,-1}; constexpr array<int,8> DY8={-1,-1,0,1,1,1,0,-1}; inline int popcnt(ll n){return __builtin_popcountll(n);} template<class T> inline bool chmax(T& a,const T& b){return a<b?a=b,true:false;} template<class T> inline bool chmin(T& a,const T& b){return b<a?a=b,true:false;} #define rep(i,s,n) for(ll i=(ll)(s);i<(ll)(n);i++) #define rrep(i,s,n) for(ll i=(ll)(s);i>=(ll)(n);i--) void _main(); int main(){ cin.tie(nullptr); ios_base::sync_with_stdio(false); cout<<fixed<<setprecision(16); _main(); } void _main(){ int N, M; cin >> N >> M; vector<ll> A(N); rep(i,0,N) cin >> A[i]; vector<tuple<int,int,ll>> edge; graph<int> rev(N); rep(i,0,M){ int a, b; cin >> a >> b; a--; b--; ll c; cin >> c; edge.emplace_back(a, b, A[b]-c); rev[b].emplace_back(a); } vector<bool> used(N); queue<int> que; used[N-1] = true; que.emplace(N-1); while(!que.empty()){ int v = que.front(); que.pop(); for(int nv:rev[v]){ if(used[nv]) continue; used[nv] = true; que.emplace(nv); } } bool inf = true; vector<ll> dist(N, -INF64); vector<bool> able(N); dist[0] = A[0]; able[0] = true; rep(i,0,N+10){ bool ok = true; for(auto [v, nv, c]:edge) if(able[v] && used[v] && used[nv]){ able[nv] = true; if(chmax(dist[nv], dist[v]+c)) ok = false; } if(ok){ inf = false; break; } } if(inf) cout << "inf" << endl; else cout << dist[N-1] << endl; }