Submission #9272

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
9272	2014-09-28T05:12:03 Z	effserv	Your life (kriii2_Y)	C++	4 / 4	80 ms	6852 KB

Y

/* 문제


*/


// 2014.

#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <functional>
#include <cstring>
#include <string>
#include <map>

using namespace std;

#define maxS	100001

vector <int> x[maxS];
queue <int> qu;

int N, M , ans = 2100000000, st;

bool visited[maxS];

int cmp1(int i, int j)
{
	return i > j;
}

void bfs()
{
	qu.push(1);
	st = 1;
	int m = 0;

	while (!qu.empty())
	{
		int tmp = qu.front();
		qu.pop();

		if (visited[tmp] == true)
			continue;

		visited[tmp] = true;

		if (st == tmp)
		{
			m++;
			st = -1;
		}

		int sz = x[tmp].size();

		for (int i = 0; i < sz; i++)
		{
			if (x[tmp][i] == N)
			{
				ans = m;
				return;
			}

			if (visited[x[tmp][i]] == false)
			{
				if (st == -1)
					st = x[tmp][i];

				qu.push(x[tmp][i]);
			}
		}
	}

	return;
}

int main()
{

	scanf("%d%d", &N, &M);

	for (int i = 0; i < M; i++)
	{
		int n, m;
		scanf("%d%d", &n, &m);
		x[n].push_back(m);
	}
	
	for (int i = 1; i <= N; i++)
		sort(x[i].begin(), x[i].end(),cmp1);

	bfs();

	if (ans == 2100000000)
		printf("-1\n");
	else
		printf("%d\n", ans);

	return 0;
}

Subtask #1

1.0 / 1.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	3684 KB	Output is correct
2	Correct	0 ms	3684 KB	Output is correct
3	Correct	0 ms	3684 KB	Output is correct
4	Correct	0 ms	3684 KB	Output is correct
5	Correct	0 ms	3684 KB	Output is correct
6	Correct	0 ms	3684 KB	Output is correct
7	Correct	0 ms	3684 KB	Output is correct
8	Correct	0 ms	3684 KB	Output is correct
9	Correct	0 ms	3684 KB	Output is correct
10	Correct	20 ms	4212 KB	Output is correct

Subtask #2

3.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	3684 KB	Output is correct
2	Correct	36 ms	6720 KB	Output is correct
3	Correct	64 ms	6720 KB	Output is correct
4	Correct	52 ms	6720 KB	Output is correct
5	Correct	48 ms	6720 KB	Output is correct
6	Correct	40 ms	6720 KB	Output is correct
7	Correct	44 ms	6720 KB	Output is correct
8	Correct	72 ms	6852 KB	Output is correct
9	Correct	44 ms	6720 KB	Output is correct
10	Correct	80 ms	6456 KB	Output is correct