医院建设网站意义,公司网页设计费计入什么科目,科技帝国从高分子材料开始,如何备份网站 整站文章目录一、题目1、原题链接2、题目描述二、解题报告1、思路分析2、时间复杂度3、代码详解三、知识风暴Floyd 算法Spfa 算法一、题目
1、原题链接 4074. 铁路与公路 2、题目描述 某国家有 n 个城市#xff08;编号 1∼n#xff09;和 m 条双向铁路。 每条铁路连接两个不同的…
文章目录一、题目1、原题链接2、题目描述二、解题报告1、思路分析2、时间复杂度3、代码详解三、知识风暴Floyd 算法Spfa 算法一、题目
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≤100≤m≤10。 所有测试点满足 2≤n≤4000≤m≤n(n−1)/21≤u,v≤n。 输入样例1 4 2
1 3
3 4输出样例1 2输入样例2 4 6
1 2
1 3
1 4
2 3
2 4
3 4输出样例2 -1输入样例3 5 5
4 2
3 5
4 5
5 1
1 2输出样例3 3二、解题报告
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 iostream
#include cstring
#include algorithm
using namespace std;
const int N410;
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 k1;kn;k){for(int i1;in;i){for(int j1;jn;j){d[i][j]min(d[i][j],d[i][k]d[k][j]);}}}return d[1][n];
}
int main(){cinnm;memset(f,0x3f,sizeof f);memset(g,0x3f,sizeof g);while(m--){int u,v;cinuv;f[u][v]f[v][u]1; //无向边存两个方向}for(int i1;in;i){for(int j1;jn;j){if(i!jf[i][j]!1){ //如果不是自环而且i和j之间没有铁路的话i和j之间存在一条公路g[i][j]1;}}}int ansmax(floyd(f),floyd(g)); //时间取两者时间的最大值if(ans0x3f3f3f3f) cout-1; //如果从城市1到城市n的时间为正无穷说明无法从城市1到达城市nelse coutans;return 0;
}Spfa算法求解
#include iostream
#include cstring
#include algorithm
#include queue
using namespace std;
const int N410,M160010;
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){ //flagfalse表示走铁路,flagtrue表示走公路//如果走铁路而且城市1和城市n之间有铁路或者如果走公路而且城市1和城市n之间有公路直接返回最小时间花费1即可if(!flagg[1][n]||flag!g[1][n]) return 1;memset(dist,0x3f,sizeof dist);queueint q;q.push(1);st[1]true;dist[1]0;while(!q.empty()){int tq.front();q.pop();st[t]false;for(int ih[t];i!-1;ine[i]){int je[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(){cinnm;memset(h1,-1,sizeof h1);memset(h2,-1,sizeof h2);while(m--){int u,v;cinuv;add(h1,u,v),add(h1,v,u); //无向边添加两次g[u][v]g[v][u]true; //标记uv两点间有铁路}for(int i1;in;i){for(int j1;jn;j){if(!g[i][j]){ //如果i,j之间没有铁路则为ij之间添加一条无向公路add(h2,i,j),add(h2,j,i);}}}int ansmax(spfa(h1,false),spfa(h2,true)); //取两者时间最大值即可if(ans0x3f3f3f3f) cout-1; //如果无解输出-1即可else coutans;return 0;
}三、知识风暴 Floyd 算法 基本思想基于动态规划首先记录两点之间无其他中间点的最短距离然后在其中加入中间点之后如果加入中间点之后两点之间的最短距离更短则更新按上述流程遍历完所有可能路径算法结束。 Spfa 算法 参考我的这篇文章即可
