Submission #9314

#	Time	Username	Problem	Language	Result	Execution time	Memory
9314		dominyellow	Your life (kriii2_Y)	C++98	0 / 4	0 ms	1248 KiB

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<=situ_count;  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", &situ_count, &goal_num);

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

	dist_vec.resize(situ_count+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("%d\n", dist_vec[goal_num]);
	}
	else{
		printf("-1\n");
	}
}

• Subtask 1: 0 / 1
• Subtask 2: 0 / 3