結果
問題 | No.2712 Play more! |
ユーザー | MM |
提出日時 | 2024-03-31 15:11:08 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,792 bytes |
コンパイル時間 | 4,021 ms |
コンパイル使用メモリ | 239,672 KB |
実行使用メモリ | 141,988 KB |
最終ジャッジ日時 | 2024-09-30 20:21:50 |
合計ジャッジ時間 | 7,465 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
13,640 KB |
testcase_01 | AC | 1 ms
6,820 KB |
testcase_02 | AC | 2 ms
6,816 KB |
testcase_03 | TLE | - |
testcase_04 | -- | - |
testcase_05 | -- | - |
testcase_06 | -- | - |
testcase_07 | -- | - |
testcase_08 | -- | - |
testcase_09 | -- | - |
testcase_10 | -- | - |
testcase_11 | -- | - |
testcase_12 | -- | - |
testcase_13 | -- | - |
testcase_14 | -- | - |
testcase_15 | -- | - |
testcase_16 | -- | - |
testcase_17 | -- | - |
testcase_18 | -- | - |
testcase_19 | -- | - |
testcase_20 | -- | - |
testcase_21 | -- | - |
testcase_22 | -- | - |
testcase_23 | -- | - |
testcase_24 | -- | - |
testcase_25 | -- | - |
testcase_26 | -- | - |
testcase_27 | -- | - |
testcase_28 | -- | - |
testcase_29 | -- | - |
testcase_30 | -- | - |
testcase_31 | -- | - |
testcase_32 | -- | - |
testcase_33 | -- | - |
testcase_34 | -- | - |
testcase_35 | -- | - |
コンパイルメッセージ
main.cpp: In function 'int main()': main.cpp:36:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions] 36 | auto [tmp,pos] = pq.top(); | ^ main.cpp:61:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions] 61 | auto [tmp,pos] = pq.top(); | ^
ソースコード
#include<bits/stdc++.h> #include<atcoder/all> #define chmin(x,y) (x) = min((x),(y)) #define chmax(x,y) (x) = max((x),(y)) #define ld long double using namespace std; using namespace atcoder; using ll = long long; using mint = modint998244353; const ll mod = 998244353; using Graph = vector<vector<pair<int,int>>>; //using Graph = vector<vector<int>>; const vector<int> dx = {1,0,-1,0}, dy = {0,1,0,-1}; int main(){ // input int N,M; cin >> N >> M; vector<int> A(N); for(int i = 0; i < N; i++) cin >> A[i]; Graph G(N); while(M--){ int a,b,c; cin >> a >> b >> c; G[--a].emplace_back(--b,c); } // prep bool inf = 0; for(int i = 0; i < N; i++){ // vector<bool> seen(N, false); // 既に見たことがある頂点か記録する priority_queue<pair<ll,int>> pq; pq.emplace(0,i); vector<ll> satis(N,-9e18); satis[i] = 0; while(!pq.empty() && !inf){ auto [tmp,pos] = pq.top(); pq.pop(); for(auto p : G[pos]){ auto nxt = p.first, cost = p.second; if(satis[nxt] < tmp + A[nxt] - cost){ pq.emplace(tmp+A[nxt]-cost,nxt); satis[nxt] = tmp+A[nxt]-cost; } if(nxt == i){ if(tmp + A[i] - cost > 0){ inf = 1; break; } } } } } // output if(inf) cout << "inf" << endl; else{ priority_queue<pair<ll,int>> pq; pq.emplace(A[0],0); vector<ll> ans(N,-9e18); ans[0] = A[0]; while(!pq.empty()){ auto [tmp,pos] = pq.top(); pq.pop(); for(auto p : G[pos]){ auto nxt = p.first, cost = p.second; if(ans[nxt] < tmp + A[nxt] - cost){ pq.emplace(tmp+A[nxt]-cost,nxt); ans[nxt] = tmp+A[nxt]-cost; } } } cout << ans[N-1] << endl; } }