1.601A The Two Routes
其实对于边权为1的最短路用bfs也是可以的,但是为了练习还是用了dijkstra啦~
#include <iostream>
#include <string.h>
#include <algorithm>
#include <stdio.h>
using namespace std;
const int inf=0x3f3f3f3f;
bool e[410][410];
int dis1[410],dis2[410];
bool vis1[410],vis2[410];
int n,m;
void dijkstra(int u){
memset(dis1,0x3f,sizeof(dis1));
memset(dis2,0x3f,sizeof(dis2));
memset(vis1,false,sizeof(vis1));
memset(vis2,false,sizeof(vis2));
dis1[u]=dis2[u]=0;
for(int i=0;i<n;++i){
int mind=inf,mint=-1;
for(int j=1;j<=n;++j){
if(!vis1[j]&&dis1[j]<mind){
mind=dis1[j];
mint=j;
}
}
if(mint==-1)break;
vis1[mint]=true;
for(int j=1;j<=n;++j){
if(!vis1[j]&&e[j][mint]&&dis1[j]>dis1[mint]+1){
dis1[j]=dis1[mint]+1;
}
}
}
for(int i=0;i<n;++i){
int mind=inf,mint=-1;
for(int j=1;j<=n;++j){
if(!vis2[j]&&dis2[j]<mind){
mind=dis2[j];
mint=j;
}
}
if(mint==-1)break;
vis2[mint]=true;
for(int j=1;j<=n;++j){
if(!vis2[j]&&!e[j][mint]&&dis2[j]>dis2[mint]+1){
dis2[j]=dis2[mint]+1;
}
}
}
}
int main(){
cin>>n>>m;
int u,v;
for(int i=0;i<m;++i){
cin>>u>>v;
e[u][v]=e[v][u]=true;
}
dijkstra(1);
int ans=max(dis1[n],dis2[n]);
ans==inf?cout<<-1<<endl:cout<<ans<<endl;
return 0;
}
网友评论