結果
問題 |
No.2712 Play more!
|
ユーザー |
|
提出日時 | 2024-03-31 14:58:29 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,792 bytes |
コンパイル時間 | 4,889 ms |
コンパイル使用メモリ | 321,740 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-09-30 23:48:53 |
合計ジャッジ時間 | 6,448 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 32 WA * 1 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/all> using mint = atcoder::modint998244353; // using mint = atcoder::modint1000000007; using namespace atcoder; using namespace std; #define rep(i,n) for (int i = 0; i < n; i++) using ll = long long; set<char> abc = {'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'}; const int inf =1e9; const ll infl = 4e18; template <typename T> bool chmax(T &a, const T& b) {if (a < b) {a = b; return true;}return false; } template <typename T> bool chmin(T &a, const T& b) {if (a > b) {a = b; return true;}return false;} int main(){ int N,M; cin >> N >> M; vector<ll> A(N);rep(i,N) cin >> A[i]; vector<vector<pair<int,ll>>> G(N); vector<vector<int>> G2(N); rep(i,M){ int a,b; ll c; cin >> a >> b >> c; a--;b--; G[a].push_back({b,A[b]-c}); G2[b].push_back(a); } vector<int> dist(N,inf); dist[N-1]=0; queue<int> que; que.push(N-1); while (!que.empty()){ int v = que.front(); que.pop(); for (auto e:G2[v]){ if (dist[e]==inf){ dist[e]=dist[v]+1; que.push(e); } } } vector<ll> dp(N,-infl); dp[0]=A[0]; rep(i,2*N){ vector<ll> dp2; dp2=dp; rep(j,N-1){ for (auto e:G[j]){ if (dp[j]==-infl) continue; if (i>=N && dist[e.first]!=inf){ if (dp2[e.first]<dp[j]+e.second){ cout << "inf" << endl; return 0; } } chmax(dp2[e.first],dp[j]+e.second); } } swap(dp,dp2); } cout << dp[N-1] << endl; }