結果
問題 |
No.2565 はじめてのおつかい
|
ユーザー |
|
提出日時 | 2023-12-02 15:44:23 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 94 ms / 2,000 ms |
コード長 | 1,344 bytes |
コンパイル時間 | 2,219 ms |
コンパイル使用メモリ | 203,044 KB |
最終ジャッジ日時 | 2025-02-18 04:53:35 |
ジャッジサーバーID (参考情報) |
judge3 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 50 |
ソースコード
#include <bits/stdc++.h> using namespace std; int main() { int N, M; cin >> N >> M; vector<vector<int>> G(N); for (int i = 0; i < M; i++) { int u, v; cin >> u >> v; u--, v--; G[u].push_back(v); // G[v].push_back(u); } const int inf = 10000000; queue<int> que; vector<int> dist1(N, inf), dist2(N, inf), dist3(N, inf); que.push(0); dist1[0] = 0; while (!que.empty()) { int cur = que.front(); que.pop(); for (auto nxt : G[cur]) { if (dist1[nxt] > dist1[cur] + 1) { que.push(nxt); dist1[nxt] = dist1[cur] + 1; } } } que.push(N - 2); dist2[N - 2] = 0; while (!que.empty()) { int cur = que.front(); que.pop(); for (auto nxt : G[cur]) { if (dist2[nxt] > dist2[cur] + 1) { que.push(nxt); dist2[nxt] = dist2[cur] + 1; } } } que.push(N - 1); dist3[N - 1] = 0; while (!que.empty()) { int cur = que.front(); que.pop(); for (auto nxt : G[cur]) { if (dist3[nxt] > dist3[cur] + 1) { que.push(nxt); dist3[nxt] = dist3[cur] + 1; } } } int ans = min(dist1[N - 2] + dist2[N - 1] + dist3[0], dist1[N - 1] + dist3[N - 2] + dist2[0]); if (ans >= inf) { ans = -1; } cout << ans << endl; return 0; } // iku junban // 1 -> N - 1 -> N -> 1 // 1 -> N -> N - 1 -> 1