Submission #9247

#	Time	Username	Problem	Language	Result	Execution time	Memory
9247		veckal	Your life (kriii2_Y)	C++14	4 / 4	88 ms	7272 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, -1);
	vector<bool> discovered(n);
	discovered[0] = 1;
	dist[0] = 0;
	queue<int> q;
	q.push(0);
	while(!q.empty()) {
		int here = q.front();
		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);
		}
	}
	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: 1 / 1
• Subtask 2: 3 / 3