Submission #9443

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
9443	2014-09-28T06:28:51 Z	dominyellow	Your life (kriii2_Y)	C++	1 / 4	36 ms	262144 KB

Y

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

using namespace std;

int p;
int minn;
int situ_count, goal_num;
queue<int> que;
map<int, bool> is_visited_map;
vector<vector<int> > graph;
vector<int> dist_vec;
int shortest_count;

void dijkstra(){
	while(!que.empty()){
		que.pop();
	}
	is_visited_map.clear();
	dist_vec.resize(goal_num+1, 987654321);
	dist_vec[1] = 0;
	int i, j;
	for(i=1; i<=situ_count; i++){
		minn = 987654321;
		for(j=1; j<=situ_count; j++){
			if(is_visited_map.count(j) == 0 && dist_vec[j] < 987654321){
				minn = dist_vec[j];
				p = j;
			}
		}
		is_visited_map[p] = true;
		for(j=1; j<=situ_count; j++){
			if(graph[p][j] == 1){
				if(is_visited_map.count(j) == 0 && dist_vec[j] > dist_vec[p] + 1){
					dist_vec[j] = dist_vec[p] + 1;
				}
			}
		}
	}
	return;
}

bool bfs_shortest(){
	int pos = que.front();
	que.pop();

	is_visited_map[pos] = true;

	int ret=false;
	if(pos == goal_num){
		return true;
	}

	int i;
	bool tmp_chk = false;
	for(i=1; i<=goal_num;  i++){
		if(graph[pos][i] == 1 && is_visited_map.count(i) == 0){
			que.push(i);
			if(dist_vec[pos] + 1 < dist_vec[i]){
				dist_vec[i] = dist_vec[pos] + 1;
			}
			tmp_chk = true;
			shortest_count += 1;
		}
	}
	if(que.empty()){
		return false;
	}
	ret |= bfs_shortest();
	return ret;

}

int main(void){
	scanf("%d%d", &goal_num, &situ_count);

	graph.resize(goal_num+1);
	for(int i=0; i<=goal_num; i++){
		graph[i].resize(goal_num+1, 0);
	}

	dist_vec.resize(goal_num+1, 987654321);
	int tmpa, tmpb;

	for(int i=0; i<situ_count; i++){
		scanf("%d%d", &tmpa, &tmpb);
		graph[tmpa][tmpb] = 1;
	}

	shortest_count = 0;
	que.push(1);
	dist_vec[1] = 0;

	if(!bfs_shortest()){
		printf("-1\n");
	}
	else{
		//dijkstra();
		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	1252 KB	Output is correct
2	Correct	0 ms	1252 KB	Output is correct
3	Correct	0 ms	1252 KB	Output is correct
4	Correct	0 ms	1252 KB	Output is correct
5	Correct	0 ms	1252 KB	Output is correct
6	Correct	0 ms	1252 KB	Output is correct
7	Correct	0 ms	1252 KB	Output is correct
8	Correct	0 ms	1252 KB	Output is correct
9	Correct	0 ms	1252 KB	Output is correct
10	Correct	20 ms	1252 KB	Output is correct

Subtask #2

0.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Memory limit exceeded	36 ms	262144 KB	Memory limit exceeded
2	Halted	0 ms	0 KB	-