結果
問題 | No.2565 はじめてのおつかい |
ユーザー |
|
提出日時 | 2023-12-02 15:07:46 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 52 ms / 2,000 ms |
コード長 | 985 bytes |
コンパイル時間 | 2,301 ms |
コンパイル使用メモリ | 200,664 KB |
最終ジャッジ日時 | 2025-02-18 04:16:20 |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 50 |
ソースコード
#include <bits/stdc++.h>using namespace std;int main(){ios::sync_with_stdio(false);cin.tie(0);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].emplace_back(v);}auto bfs = [&](int fr){vector<int> dist(n, 1 << 29);queue<int> que;dist[fr] = 0;que.emplace(fr);while(!que.empty()){int v = que.front();que.pop();for(auto &&u : g[v]){if(dist[v] + 1 >= dist[u]) continue;dist[u] = dist[v] + 1;que.emplace(u);}}return dist;};vector<vector<int>> dp(3);dp[0] = bfs(0);dp[1] = bfs(n - 2);dp[2] = bfs(n - 1);int ans = min(dp[0][n - 2] + dp[1][n - 1] + dp[2][0], dp[0][n - 1] + dp[2][n - 2] + dp[1][0]);if(ans >> 29) ans = -1;cout << ans << '\n';}