답안 #9236

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
9236	2014-09-28T04:56:42 Z	silas	Your life (kriii2_Y)	C++	4 / 4	212 ms	7580 KB

Y

#include <iostream>
#include <string.h>
#include <queue>
#include <vector>
#include <utility>
#define Nsize 100001
using namespace std;

int N, M; // N : 노드의 갯수, 선 갯수
vector<int> arr[Nsize];
int dist[Nsize];

int BFS(int cur) {
	queue<pair<int,int> > que;
	que.push(make_pair(1,0));
	while (!que.empty()) {
		int out = que.front().first;
		int out_dist = que.front().second + 1;
		que.pop();
		for (int i = 0 ; i < arr[out].size(); i++) {
			if (arr[out][i] == N) {
				return out_dist;
			}
			if (dist[arr[out][i]] == -1) {
				dist[arr[out][i]] = out_dist;
				que.push(make_pair(arr[out][i], out_dist));
			}
		}
	}
	return -1;
}

int main() {
	memset(dist, -1, sizeof(dist));
	cin >> N >> M;
	int temp1, temp2;
	for (int i = 0 ; i < M; i++) {
		cin >> temp1 >> temp2;
		arr[temp1].push_back(temp2);
	}
	cout << BFS(1) << endl;
	return 0;
}

Subtask #1

1.0 / 1.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	4412 KB	Output is correct
2	Correct	0 ms	4412 KB	Output is correct
3	Correct	0 ms	4412 KB	Output is correct
4	Correct	0 ms	4412 KB	Output is correct
5	Correct	0 ms	4412 KB	Output is correct
6	Correct	0 ms	4412 KB	Output is correct
7	Correct	0 ms	4412 KB	Output is correct
8	Correct	0 ms	4412 KB	Output is correct
9	Correct	0 ms	4412 KB	Output is correct
10	Correct	64 ms	4948 KB	Output is correct

Subtask #2

3.0 / 3.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	4412 KB	Output is correct
2	Correct	104 ms	7448 KB	Output is correct
3	Correct	164 ms	7448 KB	Output is correct
4	Correct	136 ms	7448 KB	Output is correct
5	Correct	148 ms	7448 KB	Output is correct
6	Correct	96 ms	7448 KB	Output is correct
7	Correct	120 ms	7448 KB	Output is correct
8	Correct	208 ms	7580 KB	Output is correct
9	Correct	144 ms	7448 KB	Output is correct
10	Correct	212 ms	7184 KB	Output is correct