結果
問題 |
No.2712 Play more!
|
ユーザー |
![]() |
提出日時 | 2024-03-31 14:32:26 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,896 bytes |
コンパイル時間 | 1,003 ms |
コンパイル使用メモリ | 92,444 KB |
最終ジャッジ日時 | 2025-02-20 17:17:03 |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 31 WA * 2 |
ソースコード
#include<iostream> #include<vector> #include<set> using namespace std; vector<int> bfs(int n,int m,vector<vector<int>>rotti,int start){ vector<int>stack{start}; int iti=0,hako; set<int>irane{start}; while (stack.size()>iti){ hako=stack[iti]; for (int i=0;i<rotti[hako-1].size();i++){ if (irane.count(rotti[hako-1][i])>0)continue; irane.insert(rotti[hako-1][i]); stack.emplace_back(rotti[hako-1][i]); } iti++; } vector<int>ans(n,0); //連結してるなら1 for (int i=0;i<n;i++)if(irane.count(i+1)>0)ans[i]=1; return ans; } vector<long long> dijkstra_negative(int n,int m,vector<vector<vector<int>>>graph,int start,vector<int>num){ //連結じゃない頂点には手をださない //vector<int>numの中身はそれぞれの頂点がスタート地点から連結かどうか(連結なら1) vector<long long>amount(n,1e12); int check; amount[start-1]=0; for (int q=0;q<n+1;q++){ check=0; for (int i=0;i<n;i++){ if(num[i]==0)continue; for (int ipp=0;ipp<graph[i].size();ipp++){ if(amount[graph[i][ipp][0]-1]<=amount[i]+graph[i][ipp][1])continue; check=1; amount[graph[i][ipp][0]-1]=amount[i]+graph[i][ipp][1]; } } if(check==0)break; } //負の経路が存在する if(check==1){ amount[start-1]=-1; return amount; } return amount; } int main() { int n,m; cin >> n >> m; vector<int>A(n); vector<vector<vector<int>>>graph(n); vector<vector<int>>graph2(n); for(int i=0;i<n;i++)cin >> A[i]; for(int i=0;i<m;i++){ int a,b,c; cin >> a >> b >> c; graph[a-1].push_back({b,c-A[b-1]}); graph2[a-1].emplace_back(b); } vector<int>num=bfs(n,m,graph2,1); vector<long long>amount=dijkstra_negative(n,m,graph,1,num); if(amount[0]==-1)cout << "inf" << endl; else cout << amount[n-1]*(long long)-1+(long long)A[0] << endl; }