#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;
}
| # |
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 |
Runtime error |
0 ms |
1248 KB |
SIGSEGV Segmentation fault |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Halted |
0 ms |
0 KB |
- |
