結果

問題 No.2565 はじめてのおつかい
ユーザー forest3
提出日時 2025-03-13 11:05:51
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 984 bytes
コンパイル時間 2,055 ms
コンパイル使用メモリ 172,524 KB
実行使用メモリ 9,344 KB
最終ジャッジ日時 2025-03-13 11:06:00
合計ジャッジ時間 8,422 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 33 WA * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
#define rep(i, n) for(int i = 0; i < n; i++)

int main() {
	int N, M;
	cin >> N >> M;
	vector<vector<int>> g(N);
	rep(i, M) {
		int u, v;
		cin >> u >> v;
		u--, v--;
		g[u].push_back(v);
	}
	int INF = 1e9;
	vector<int> d(N, INF), d1(N, INF);
	using P = pair<int, int>;
	queue<P> q;
	q.push(P(0, 0));
	d[0] = 0;
	while(q.size()) {
		int u, dd;
		tie(u, dd) = q.front();
		q.pop();
		for(int e : g[u]) {
			if(d[e] > dd + 1) {
				d[e] = dd + 1;
				q.push(P(e, d[e]));
			}
		}
	}
	int ans = max(d[N - 1], d[N - 2]);
	if(ans == INF) {
		cout << -1 << endl;
		return 0;
	}
	int s = N - 1;
	if(d[N - 2] > d[N - 1]) s = N - 2;
	q.push(P(s, 0));
	d1[s] = 0;
	while(q.size()) {
		int u, dd;
		tie(u, dd) = q.front();
		q.pop();
		for(int e : g[u]) {
			if(d1[e] > dd + 1) {
				d1[e] = dd + 1;
				q.push(P(e, d1[e]));
			}
		}
	}
	if(d1[0] == INF) {
		cout << -1 << endl;
		return 0;
	}
	cout << ans + d1[0] << endl;
};
0