結果
問題 |
No.2712 Play more!
|
ユーザー |
|
提出日時 | 2024-03-31 14:57:24 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 80 ms / 2,000 ms |
コード長 | 2,627 bytes |
コンパイル時間 | 2,209 ms |
コンパイル使用メモリ | 206,812 KB |
最終ジャッジ日時 | 2025-02-20 17:32:17 |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 33 |
ソースコード
#include <bits/stdc++.h> // clang-format off using namespace std; using ll=long long; using ull=unsigned long long; using pll=pair<ll,ll>; const ll INF=4e18; void print0(){}; template<typename H,typename... T> void print0(H h,T... t){cout<<h;print0(t...);} void print1(){print0("\n");}; template<typename H,typename... T>void print1(H h,T... t){print0(h);if(sizeof...(T)>0)print0(" ");print1(t...);} void ioinit() { cout<<fixed<<setprecision(15); cerr<<fixed<<setprecision(6); ios_base::sync_with_stdio(0); cin.tie(0); } #define debug1(a) { cerr<<#a<<":"<<a<<endl; } #define debug2(a,b) { cerr<<#a<<":"<<a<<" "<<#b<<":"<<b<<endl; } #define debug3(a,b,c) { cerr<<#a<<":"<<a<<" "<<#b<<":"<<b<<" "<<#c<<":"<<c<<endl; } #define debug4(a,b,c,d) { cerr<<#a<<":"<<a<<" "<<#b<<":"<<b<<" "<<#c<<":"<<c<<" "<<#d<<":"<<d<<endl; } // clang-format on struct edg { ll id; ll u; ll v; ll c; }; ll n; vector<vector<edg>> edgmap(2502); vector<edg> edges; // 各ノードからゴール(n-1)に到達できるか判定 vector<bool> arrive(2502); vector<bool> search_arrive(2502); bool dfs_arrive(ll u) { if (u == n - 1) { return true; } if (search_arrive[u]) { return false; } search_arrive[u] = true; for (auto e : edgmap[u]) { if (dfs_arrive(e.v)) { return true; } } return false; } // s->各頂点の最長路 vector<ll> bf_max(ll s) { vector<ll> dp(n, -INF); dp[s] = 0; for (ll op = 0; true; op++) { if (op > n) { return vector<ll>(); } bool updated = false; for (auto e : edges) { if (!arrive[e.u] || !arrive[e.v]) continue; // ゴール(n-1)に到達できないノードは無視する if (dp[e.u] != -INF && dp[e.v] < dp[e.u] + e.c) { updated = true; dp[e.v] = dp[e.u] + e.c; } } if (!updated) break; } return dp; } int main() { ioinit(); ll m; cin >> n >> m; vector<ll> a(n); for (ll i = 0; i < n; i++) { cin >> a[i]; } for (ll e = 0; e < m; e++) { ll u, v, c; cin >> u >> v >> c; u--; v--; ll score = -c + a[v]; edg ed = {e, u, v, score}; edges.push_back(ed); edgmap[u].push_back(ed); } for (ll i = 0; i < n; i++) { search_arrive.resize(0); search_arrive.resize(n + 1); arrive[i] = dfs_arrive(i); } auto result = bf_max(0); if (result.size() == 0) { print1("inf"); } else { print1(result[n - 1] + a[0]); } return 0; }