题目链接(Codeforces):http://codeforces.com/problemset/problem/601/A
题目链接(51nod):https://www.51nod.com/Challenge/Problem.html#!#problemId=1649
51nod的题面是中文的
思路就是两种车各跑一遍dij,就是处理一下边就好了。
AC代码:
#include <bits/stdc++.h>
#define maxm 200005
#define maxn 405
#define inf 0x3f3f3f3f
using namespace std;
struct Node{
int to,w,next;
bool operator < (const Node &a) const {
return a.w < w;
}
}Edge[maxm],S,Next;
int head[maxm],num;
int dist[maxm];
bool a[maxn][maxn],vis[maxm];
int n,m;
void init(){
for(int i=0;i<=n;i++){
head[i] = -1;
}
num = 0;
}
void add(int u,int v){
Edge[num].w = 1;
Edge[num].to = v;
Edge[num].next = head[u];
head[u] = num ++;
}
void dijkstra(int s){
for(int i=0;i<=n;i++){
dist[i] = inf;
vis[i] = false;
}
priority_queue<Node> q;
S.to = s;
dist[s] = 0;
q.push(S);
while(!q.empty()){
int u = q.top().to;
q.pop();
if(vis[u]) continue;
vis[u] = true;
for(int i=head[u];i!=-1;i=Edge[i].next){
int v = Edge[i].to;
if(!vis[v] && dist[v] > dist[u] + Edge[i].w){
dist[v] = dist[u] + Edge[i].w;
Next.to = v;
Next.w = dist[v];
q.push(Next);
}
}
}
}
int main()
{
// init();
scanf("%d%d",&n,&m);
init();
for(int i=0;i<m;i++){
int u,v;
scanf("%d%d",&u,&v);
a[u][v] = a[v][u] = true;
add(u, v);
add(v, u);
}
dijkstra(1);
int ans1 = dist[n];
init();
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
if(a[i][j] == false){
add(i, j);
add(j, i);
}
}
}
dijkstra(1);
int ans2 = dist[n];
printf("%d\n",max(ans1, ans2) == inf ? -1 : max(ans1, ans2));
return 0;
}