oj.uz

답안 #9182

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
9182 2014-09-28T04:26:25 Z corea Your life (kriii2_Y) C++14
4 / 4
 88 ms 6952 KB 
#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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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