結果
問題 | No.2565 はじめてのおつかい |
ユーザー |
![]() |
提出日時 | 2023-12-02 16:01:09 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 95 ms / 2,000 ms |
コード長 | 1,094 bytes |
コンパイル時間 | 1,338 ms |
コンパイル使用メモリ | 106,932 KB |
最終ジャッジ日時 | 2025-02-18 05:07:16 |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 50 |
ソースコード
#include <iostream> #include <vector> #include <algorithm> #include <cmath> #include <set> #include <map> #include <string> #include <queue> using namespace std; int main() { int n, m; cin >> n >> m; vector to(n, vector<int>()); for (int i = 0; i < m; i++) { int u, v; cin >> u >> v; u--; v--; to[u].push_back(v); } const long long INF = 1001001001; auto bfs = [&](int s) -> vector<long long> { vector<long long> dp(n, INF); queue<int> q; q.push(s); dp[s] = 0; while (q.size()) { auto v = q.front(); q.pop(); for (auto u : to[v]) { if (dp[u] == INF) { dp[u] = dp[v] + 1; q.push(u); } } } return dp; }; auto dp0 = bfs(0); // for (int i = 0; i < n; i++) { // cout << (dp0[i] == INF ? -1ll : dp0[i]) << (i + 1 == n ? "\n" : " "); // } auto dpnp = bfs(n - 2); auto dpn = bfs(n - 1); long long ans = min({dp0[n - 2] + dpnp[n - 1] + dpn[0], dp0[n - 2] + dpnp[0] + dp0[n - 1] + dpn[0], dp0[n - 1] + dpn[n - 2] + dpnp[0]}); if (ans >= INF) ans = -1; cout << ans << endl; }