結果
問題 |
No.2565 はじめてのおつかい
|
ユーザー |
|
提出日時 | 2025-05-30 22:25:17 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 41 ms / 2,000 ms |
コード長 | 1,700 bytes |
コンパイル時間 | 2,093 ms |
コンパイル使用メモリ | 201,148 KB |
実行使用メモリ | 13,244 KB |
最終ジャッジ日時 | 2025-05-30 22:25:24 |
合計ジャッジ時間 | 6,722 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 50 |
ソースコード
#include<bits/stdc++.h> using namespace std; #define int long long #define fi first #define se second #define PB push_back #define pii pair<int, int> #define FOR(i, a, b) for (int i = (a); i <= (b); i++) #define FOD(i, a, b) for (int i = (a); i >= (b); i--) #define REP(i, n) for (int i = 0; i < (n); i++) #define ALL(x) (x).begin(), (x).end() #define __Suchi__ signed main() #define TIME (1.0 * clock()/CLOCKS_PER_SEC) const int N = 1e5+7; const int M = 1e3+1; int n, m, k; int d[N][4]; int vis[N]; vector<int> g[N]; void bfs(int s, int idx){ memset(vis, 0 , sizeof vis); queue<int> q; q.push(s); d[s][idx] = 0; while(!q.empty()){ int u = q.front(); q.pop(); if (vis[u]) continue; vis[u] = 1; for(auto v : g[u]) if (d[v][idx] > d[u][idx] + 1){ d[v][idx] = d[u][idx] + 1; q.push(v); } } } void solve(){ FOR(i,1,k){ int x,y ; cin >> x >> y; g[x].PB(y); } FOR(i,1,n) d[i][1] = d[i][2] = d[i][3] = 1000000000; bfs(1, 1); bfs(n-1, 2); bfs(n, 3); // FOR(i,1,n) cout << d[i][1] << " "; // cout << "\n"; // FOR(i,1,n) cout << d[i][2] << " "; // cout << "\n"; // FOR(i,1,n) cout << d[i][3] << " "; // cout << "\n"; // 1 -> n -> n-1 -> 1 // 1 -> n-1 -> n -> 1 int res = min(d[n-1][1] + d[n][2] + d[1][3], d[n][1] + d[n-1][3] + d[1][2]); cout << (res >= 1000000000 ? -1 : res); } __Suchi__{ ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int t = 1; FOR(i, 1, t){ cin >> n >> k; solve(); } cerr << "Time elapsed: " << TIME << "s.\n"; return (0 ^ 0); }