제출 #9239

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
9239		veckal	Your life (kriii2_Y)	C++14	0 / 4	0 ms	1240 KiB

Y

#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
const int INF = 987654321;

int n, m;
vector<vector<int>> edge;

int dijkstra() {
	vector<int> dist(n, INF);
	vector<bool> discovered(n);
	discovered[0] = 1;
	dist[0] = 0;
	queue<int> q;
	q.push(0);
	while(!q.empty()) {
		int here = q.back();
		q.pop();
		for (int i=0; i<edge[here].size(); ++i) {
			int there = edge[here][i];
			if (discovered[there]) continue;
			dist[there] = dist[here] + 1;
			discovered[there] = 1;
			q.push(there);
		}
	}
	if (dist[n-1] == INF) return -1;
	return dist[n-1];
}

int main() {
	scanf("%d%d", &n, &m);
	edge = vector<vector<int>>(n);
	for (int i=0; i<m; ++i) {
		int x, y;
		scanf("%d%d", &x, &y);
		--x; --y;
		edge[x].push_back(y);
	}
	printf("%d\n", dijkstra());
	return 0;
}

• Subtask 1: 0 / 1
• Subtask 2: 0 / 3