結果
問題 |
No.2915 辺更新価値最大化
|
ユーザー |
![]() |
提出日時 | 2024-10-06 17:53:54 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,919 bytes |
コンパイル時間 | 1,769 ms |
コンパイル使用メモリ | 124,644 KB |
実行使用メモリ | 10,496 KB |
最終ジャッジ日時 | 2024-10-06 17:54:01 |
合計ジャッジ時間 | 6,725 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 19 WA * 8 TLE * 1 |
ソースコード
#include<iostream> #include<vector> #include<algorithm> using namespace std; using ll = long long; #include<queue> #include<atcoder/scc> int main(){ cin.tie(nullptr); ios::sync_with_stdio(false); ll n,m,q; cin>>n>>m>>q; vector<vector<int>> g(n); vector<ll> u(m),v(m),w(m); atcoder::scc_graph s(n); for(int i = 0;i<m;i++){ cin>>u[i]>>v[i]>>w[i]; u[i]--;v[i]--; g[u[i]].push_back(i); s.add_edge(u[i],v[i]); } vector<int> now(m,0); auto use = s.scc(); vector<int> cnt(n,0); for(int i = 0;i<use.size();i++) for(auto ni:use[i]) cnt[ni] = i; // for(int i = 0;i<n;i++) cout<<i<<" "<<cnt[i]<<endl; while(q--){ { int j; cin>>j; j--; now[j] ^= 1; } vector<ll> can(n,-1e18); can[0] = 0; for(auto p:use){ priority_queue<pair<ll,ll>> que; // vector<int> que; for(int j:p) if(can[j]!=-1e18) que.push({can[j],j}); while(que.size()){ // cout<<i<<endl; int ni = que.top().second; auto nn = que.top(); que.pop(); if(nn.first!=can[ni]) continue; for(auto id:g[ni]){ int to = v[id]; if(now[id]==1) continue; if(cnt[to]==cnt[ni]){ if(can[to]<can[ni]+w[id]){ can[to] = max(can[to],can[ni] + w[id]); que.push({can[to],to}); } }else{ // cout<<id<<endl; can[to] = max(can[to],can[ni]+w[id]); } } } } ll ans = can[n-1]; if(ans==-1e18) cout<<"Nan\n"; else cout<<ans<<endl; //return 0; } }