結果
問題 |
No.2565 はじめてのおつかい
|
ユーザー |
![]() |
提出日時 | 2024-03-24 14:02:38 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 108 ms / 2,000 ms |
コード長 | 1,279 bytes |
コンパイル時間 | 1,335 ms |
コンパイル使用メモリ | 120,536 KB |
最終ジャッジ日時 | 2025-02-20 13:38:10 |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 50 |
ソースコード
#define _USE_MATH_DEFINES #include <iostream> #include <string> #include <algorithm> #include <vector> #include <queue> #include <math.h> #include <cmath> #include <stack> #include <map> #include <set> #include <numeric> #include <iomanip> #include <climits> #include <functional> #include <cassert> #include <tuple> using namespace std; using ll = long long; int N, M; vector<int> G[101010]; void wfs(int t, vector<int> &vis) { vis[t] = 0; queue<int> q; q.push(t); while(!q.empty()) { int v = q.front(); q.pop(); for(int ne : G[v]) { if(vis[ne] != -1) continue; vis[ne] = vis[v]+1; q.push(ne); } } } int main() { cin >> N >> M; for(int i = 0; i < M; ++i) { int u,v; cin >> u >> v; G[u].push_back(v); } vector<int> vis1(N+1, -1); vector<int> visN_1(N+1, -1); vector<int> visN(N+1, -1); wfs(1,vis1); wfs(N-1,visN_1); wfs(N,visN); int mn = 1e9; if(vis1[N-1] != -1 && visN_1[N] != -1 && visN[1] != -1) mn = min(mn, vis1[N-1]+visN_1[N]+visN[1]); if(vis1[N] != -1 && visN[N-1] != -1 && visN_1[1] != -1) mn = min(mn, vis1[N]+visN[N-1]+visN_1[1]); cout << (mn != 1e9 ? mn : -1) << endl; }