一、题目
1、原题链接
4074. 铁路与公路
2、题目描述
某国家有 n 个城市（编号 1∼n）和 m 条双向铁路。
每条铁路连接两个不同的城市，没有两条铁路连接同一对城市。
除了铁路以外，该国家还有公路。
对于每对不同的城市 x,y，当且仅当它们之间没有铁路时，它们之间会存在一条双向公路。
经过每条铁路或公路都需要花费 1 小时的时间。
现在有一列火车和一辆汽车同时离开城市 1，它们的目的地都是城市 n。
它们不会在途中停靠（但是可以在城市 n 停靠）。
火车只能沿铁路行驶，汽车只能沿公路行驶。
请你为它们规划行进路线，每条路线中可重复经过同一条铁路或公路，但是为了避免发生事故，火车和汽车不得同时到达同一个城市（城市 n 除外）。
请问，在这些条件的约束下，两辆车全部到达城市 n 所需的最少小时数，即求更慢到达城市 n 的那辆车所需的时间的最小值。
注意，两辆车允许但不必要同时到达城市 n。
输入格式
第一行包含整数 n 和 m。
接下来 m 行，每行包含两个整数 u,v，表示城市 u 和城市 v 之间存在一条铁路。
输出格式
一个整数，表示所需的最少小时数。
如果至少有一辆车无法到达城市 n，则输出 −1。
数据范围
前 6 个测试点满足 2≤n≤10，0≤m≤10。
所有测试点满足 2≤n≤400，0≤m≤n(n−1)/2，1≤u,v≤n。
输入样例1：
4 2
1 3
3 4
输出样例1：
2
1
输入样例2：
4 6
1 2
1 3
1 4
2 3
2 4
3 4
输出样例2：
-1
1
输入样例3：
5 5
4 2
3 5
4 5
5 1
1 2
输出样例3：
3
1
二、解题报告
1、思路分析
思路来源：y总讲解视频
y总yyds
（1）如果从城市1到城市n之间有铁路，则从城市1到城市n，火车会直接到达城市n，而汽车会走公路经过某些城市然后再到达城市n，所以火车和汽车必然不会在城市1~n（除城市1和城市n）中的任意一座城市停留。
（2）同理，如果从城市1到城市n之间有公路，汽车和火车也必然不会在城市1~n（除城市1和城市n）中的任意一座城市停留。
（3）综上，任何情况下火车和汽车从城市1到达城市n，如果可以到达，则在路径之中必然不会同时在1~n（除城市1和城市n）中的某一座城市停留。
（4）所以，题目中的约束条件始终无法满足，我们只需要求出火车和汽车分别到达城市n的最短时间，然后取最大者即可。
2、时间复杂度
Floyd算法时间复杂度为O(n3)
Spfa算法时间复杂度为O(nm)
3、代码详解
Floyd算法求解
#include
#include
#include
using namespace std;
const int N=410;
int n,m;
int f[N][N],g[N][N]; //f[i][j]存储从i城市到j城市走铁路的花费时间，如果不存在铁路则为正无穷；g[i][j]存储公路的，同理
//floyd算法求最短路
int floyd(int d[][N]){
if(d[1][n]==1) return 1; //如果城市1到城市n存在一条公路/铁路,花费时间为1，直接返回即可
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
}
}
}
return d[1][n];
}
int main(){
cin>>n>>m;
memset(f,0x3f,sizeof f);
memset(g,0x3f,sizeof g);
while(m--){
int u,v;
cin>>u>>v;
f[u][v]=f[v][u]=1; //无向边存两个方向
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(i!=j&&f[i][j]!=1){ //如果不是自环，而且i和j之间没有铁路的话，i和j之间存在一条公路
g[i][j]=1;
}
}
}
int ans=max(floyd(f),floyd(g)); //时间取两者时间的最大值
if(ans==0x3f3f3f3f) cout<<-1; //如果从城市1到城市n的时间为正无穷，说明无法从城市1到达城市n
else cout<
return 0;
}
Spfa算法求解
#include
#include
#include
#include
using namespace std;
const int N=410,M=160010;
int h1[N],h2[N],e[M],ne[M],idx; //h1[]存储每条铁路（边），h2[]存储每条公路（边），e[]存储每条边的终点，ne[]存储每条边同起点的下一条边，idx为边的编号
bool g[N][N]; //g[i][j]存储i和j之间是否存在铁路
int n,m;
bool st[N]; //st[i]存储第i个点的最短距离是否被松弛更新过
int dist[N]; //dist[i]存储从城市1到城市i的最小花费时间
//邻接表加边
void add(int h[],int a,int b){
e[idx]=b;
ne[idx]=h[a];
h[a]=idx++;
}
//spfa算法求最短路
int spfa(int h[],bool flag){ //flag=false表示走铁路,flag=true表示走公路
//如果走铁路，而且城市1和城市n之间有铁路或者如果走公路，而且城市1和城市n之间有公路，直接返回最小时间花费1即可
if(!flag&&g[1][n]||flag&&!g[1][n]) return 1;
memset(dist,0x3f,sizeof dist);
queue q;
q.push(1);
st[1]=true;
dist[1]=0;
while(!q.empty()){
int t=q.front();
q.pop();
st[t]=false;
for(int i=h[t];i!=-1;i=ne[i]){
int j=e[i];
if(dist[j]>dist[t]+1){
dist[j]=dist[t]+1;
if(!st[j]){
st[j]=true;
q.push(j);
}
}
}
}
return dist[n];
}
int main(){
cin>>n>>m;
memset(h1,-1,sizeof h1);
memset(h2,-1,sizeof h2);
while(m--){
int u,v;
cin>>u>>v;
add(h1,u,v),add(h1,v,u); //无向边，添加两次
g[u][v]=g[v][u]=true; //标记u，v两点间有铁路
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(!g[i][j]){ //如果i,j之间没有铁路，则为i，j之间添加一条无向公路
add(h2,i,j),add(h2,j,i);
}
}
}
int ans=max(spfa(h1,false),spfa(h2,true)); //取两者时间最大值即可
if(ans==0x3f3f3f3f) cout<<-1; //如果无解，输出-1即可
else cout<
return 0;
}
三、知识风暴
Floyd 算法
基本思想：基于动态规划，首先记录两点之间无其他中间点的最短距离，然后在其中加入中间点之后，如果加入中间点之后，两点之间的最短距离更短，则更新，按上述流程，遍历完所有可能路径，算法结束。
Spfa 算法
参考我的这篇文章即可
