#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");
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
1248 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
1248 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Halted |
0 ms |
0 KB |
- |
