結果
問題 | No.2565 はじめてのおつかい |
ユーザー |
|
提出日時 | 2023-12-02 16:06:56 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 94 ms / 2,000 ms |
コード長 | 1,116 bytes |
コンパイル時間 | 2,483 ms |
コンパイル使用メモリ | 202,480 KB |
最終ジャッジ日時 | 2025-02-18 05:12:37 |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 50 |
ソースコード
#include<bits/stdc++.h> using namespace std; using ll=long long; int main(){ ll n,m; cin>>n>>m; vector<vector<ll>> G(n); for(ll i=0;i<m;i++){ ll u,v; cin>>u>>v; u--; v--; G[u].push_back(v); } queue<ll> que; vector<ll> dist1(n,1e18); que.push(0); dist1[0]=0; while(que.size()){ ll q=que.front(); que.pop(); for(ll u:G[q]){ if(dist1[u]==1e18){ dist1[u]=dist1[q]+1; que.push(u); } } } vector<ll> dist2(n,1e18); que.push(n-2); dist2[n-2]=0; while(que.size()){ ll q=que.front(); que.pop(); for(ll u:G[q]){ if(dist2[u]==1e18){ dist2[u]=dist2[q]+1; que.push(u); } } } vector<ll> dist3(n,1e18); que.push(n-1); dist3[n-1]=0; while(que.size()){ ll q=que.front(); que.pop(); for(ll u:G[q]){ if(dist3[u]==1e18){ dist3[u]=dist3[q]+1; que.push(u); } } } ll ans=1e18; ans=min(ans,dist1[n-2]+dist2[n-1]+dist3[0]); ans=min(ans,dist1[n-1]+dist3[n-2]+dist2[0]); if(ans==1e18){ cout<<-1<<endl; }else{ cout<<ans<<endl; } }