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;
}