結果
問題 |
No.2712 Play more!
|
ユーザー |
![]() |
提出日時 | 2024-03-31 14:49:46 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 74 ms / 2,000 ms |
コード長 | 854 bytes |
コンパイル時間 | 2,323 ms |
コンパイル使用メモリ | 196,768 KB |
最終ジャッジ日時 | 2025-02-20 17:27:15 |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 33 |
ソースコード
#include <bits/stdc++.h> using namespace std; int main() { int N, M; cin >> N >> M; vector<long long> A(N); for(int i = 0; i < N; i++) { cin >> A[i]; } vector<int> a(M), b(M); vector<long long> c(M); for(int i = 0; i < M; i++) { cin >> a[i] >> b[i] >> c[i]; a[i]--, b[i]--; } const long long INF = 1LL<<55; vector<int> f(N), g(N); vector<long long> dp(N, INF); dp[0] = 0; f[0] = true, g[N-1] = true; for(int i = 0; i < N; i++) { for(int j = 0; j < M; j++) { f[b[j]] |= f[a[j]]; g[a[j]] |= g[b[j]]; if(dp[b[j]] > dp[a[j]]-(A[a[j]]-c[j])) { dp[b[j]] = dp[a[j]]-(A[a[j]]-c[j]); } } } for(int j = 0; j < M; j++) { if(dp[b[j]] > dp[a[j]]-(A[a[j]]-c[j]) && f[a[j]] && g[b[j]]) { cout << "inf" << endl; return 0; } } cout << A[N-1]-dp[N-1] << endl; }