結果
問題 | 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'; }