結果
問題 | No.1393 Median of Walk |
ユーザー |
|
提出日時 | 2021-02-13 04:16:29 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 133 ms / 2,000 ms |
コード長 | 1,317 bytes |
コンパイル時間 | 1,041 ms |
コンパイル使用メモリ | 89,528 KB |
実行使用メモリ | 5,568 KB |
最終ジャッジ日時 | 2024-07-20 05:30:28 |
合計ジャッジ時間 | 3,136 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 39 |
コンパイルメッセージ
main.cpp:10:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type] 10 | main() | ^~~~
ソースコード
#include<iostream>#include<queue>#include<algorithm>#include<vector>using namespace std;int N,M;int dist[1010];int ans[1010];vector<pair<int,int> >G[1010];main(){cin>>N>>M;vector<pair<int,pair<int,int> > >E(M);for(int i=0;i<M;i++){int u,v,w;cin>>u>>v>>w;u--,v--;E[i]=make_pair(w,make_pair(u,v));G[u].push_back(make_pair(v,1));}sort(E.begin(),E.end());for(int i=0;i<N;i++)ans[i]=dist[i]=2e9;dist[0]=0;{queue<int>P;P.push(0);while(!P.empty()){int u=P.front();P.pop();for(pair<int,int>e:G[u]){int v=e.first;if(dist[v]>dist[u]+e.second){dist[v]=dist[u]+e.second;P.push(v);}}}}for(pair<int,pair<int,int> >e:E){G[e.second.first].push_back(make_pair(e.second.second,-1));priority_queue<pair<int,int> >P;P.push(make_pair(-dist[e.second.first],e.second.first));while(!P.empty()){int u=P.top().second,cost=-P.top().first;P.pop();if(dist[u]<cost)continue;for(pair<int,int>e:G[u]){int v=e.first;int nxt=dist[u]+e.second;if(dist[v]>-N&&dist[v]>nxt){dist[v]=nxt;P.push(make_pair(-nxt,v));}}}for(int i=0;i<N;i++)if(dist[i]<=0){if(ans[i]==(int)2e9)ans[i]=e.first;}}for(int i=1;i<N;i++)cout<<(ans[i]<(int)2e9?ans[i]:-1)<<endl;}