Submission #9444

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
9444	2014-09-28T06:29:21 Z	dominyellow	Your life (kriii2_Y)	C++	1 / 4	40 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;


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{
		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	1248 KB	Output is correct
2	Correct	0 ms	1248 KB	Output is correct
3	Correct	0 ms	1248 KB	Output is correct
4	Correct	0 ms	1248 KB	Output is correct
5	Correct	0 ms	1248 KB	Output is correct
6	Correct	0 ms	1248 KB	Output is correct
7	Correct	0 ms	1248 KB	Output is correct
8	Correct	0 ms	1248 KB	Output is correct
9	Correct	0 ms	1248 KB	Output is correct
10	Correct	12 ms	1248 KB	Output is correct

Subtask #2

0.0 / 3.0

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