oj.uz

Submission #9757

# Submission time Handle Problem Language Result Execution time Memory
9757 2014-09-28T08:42:17 Z dominyellow Your life (kriii2_Y) C++
4 / 4
 96 ms 7600 KB 
#include <stdio.h>
#include <map>
#include <queue>
#include <set>
#include <vector>
 
using namespace std;
 
int situ_count, goal_num;
vector<vector<int> > graph;

vector<int> dijkstra(int v, int src){
	vector<int> dist(v+1,987654321);
	dist[src] = 0;

	priority_queue<pair<int,int> > p_que;
	p_que.push(make_pair(0,src));

	while(!p_que.empty()){
		int cost = -p_que.top().first;
		int here = p_que.top().second;

		p_que.pop();

		if(cost > dist[here]){
			continue;
		}
		for(int i=0;i<graph[here].size();i++){
			int there = graph[here][i];
			int nextDist = cost + 1;

			if(dist[there] > nextDist){
				dist[there] = nextDist;
				p_que.push(make_pair(-nextDist,there));
			}
		}
	}
	return dist;
}
 
int main(void){
    scanf("%d%d", &goal_num, &situ_count);
 
    graph.resize(goal_num+1);
 
    int tmpa, tmpb;
 
    for(int i=0; i<situ_count; i++){
        scanf("%d%d", &tmpa, &tmpb);
		graph[tmpa].push_back(tmpb);
    }
	vector<int> dist_vec = dijkstra(goal_num, 1);

	if(dist_vec[goal_num] == 987654321){
		printf("-1\n");
	}
	else{
		printf("%d\n", dist_vec[goal_num]);
	}
    return 0;
}

Subtask #1
1.0 / 1.0

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

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3976 KB Output is correct
2 Correct 32 ms 7012 KB Output is correct
3 Correct 64 ms 7012 KB Output is correct
4 Correct 48 ms 7012 KB Output is correct
5 Correct 64 ms 7012 KB Output is correct
6 Correct 36 ms 7012 KB Output is correct
7 Correct 32 ms 7012 KB Output is correct
8 Correct 96 ms 7600 KB Output is correct
9 Correct 40 ms 7012 KB Output is correct
10 Correct 88 ms 6748 KB Output is correct