Submission #9182

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
9182	2014-09-28T04:26:25 Z	corea	Your life (kriii2_Y)	C++14	4 / 4	88 ms	6952 KB

Y

#include <stdio.h>
#include <vector>
#include <queue>

using namespace std;

bool V[ 100003 ];

vector<int> data[ 100003 ];

priority_queue< pair<int, int> > pq;


int N, M;


int main() {
	scanf( "%d %d", &N, &M );

	while( M -- ) {
		int a, b;
		scanf( "%d %d", &a, &b );

		data[ a ].push_back( b );
	}

	pq.emplace( 0, 1 );

	while( !pq.empty() ) {
		pair<int, int> now = pq.top();
		pq.pop();

		if( now.second == N ) {
			printf( "%d\n", - now.first );
			return 0;
		}
		if( V[ now.second ] ) {
			continue;
		}
		V[ now.second ] = true;
		
		for( auto &v : data[ now.second ] ) {
			if( V[ v ] ) {
				continue;
			}
			pq.emplace( now.first - 1, v );
		}
	}

	printf( "-1\n" );
	
	return 0;
}

Subtask #1

1.0 / 1.0

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

Subtask #2

3.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	3652 KB	Output is correct
2	Correct	32 ms	6688 KB	Output is correct
3	Correct	56 ms	6688 KB	Output is correct
4	Correct	52 ms	6688 KB	Output is correct
5	Correct	64 ms	6688 KB	Output is correct
6	Correct	44 ms	6688 KB	Output is correct
7	Correct	32 ms	6688 KB	Output is correct
8	Correct	88 ms	6952 KB	Output is correct
9	Correct	44 ms	6688 KB	Output is correct
10	Correct	76 ms	6424 KB	Output is correct