最短路径问题
标签: 机试攻略 - 高分篇
学习人数: 18.2k


高清播放
赞赏支持

Floyd算法特点

1、适合求多源最短路径
2、可以求最小环
3、可以有负边权,不能有负环
4、可以求有向图的传递闭包
5、时间复杂度O(n^3)

 

单源最短路径算法的选择?

Dijkstra + 堆优化?无法处理负边权的问题
SPFA + 堆优化?期望复杂度很优秀,但是复杂度不稳定

基于本书面向的是计算机考研机试,几乎不可能出现故意构造大量数据使得SPFA超时的情况发生,就如同不可能在机试中故意构造数据使得sort函数的复杂度退化到O(n^2)一样。

当然,也为了防止本书爆红之后被出题老师故意针对,后面我们也附上Dijkstra的通用算法模板以备不时之需。

 

 

最短路
题目描述:

在每年的校赛里,所有进入决赛的同学都会获得一件很漂亮的t-shirt。但是每当我们的工作人员把上百件的衣服从商店运回到赛场的时候,却是非常累的!所以现在他们想要寻找最短的从商店到赛场的路线,你可以帮助他们吗?
输入描述:
输入包括多组数据。每组数据第一行是两个整数N、M(N<=100,M<=10000),N表示成都的大街上有几个路口,标号为1的路口是商店所在地,标号为N的路口是赛场所在地,M则表示在成都有几条路。N=M=0表示输入结束。接下来M行,每行包括3个整数A,B,C(1<=A,B<=N,1<=C<=1000),表示在路口A与路口B之间有一条路,我们的工作人员需要C分钟的时间走过这条路。
输入保证至少存在1条商店到赛场的路线。
输出描述:
对于每组输入,输出一行,表示工作人员从商店走到赛场的最短时间
输入样例#:
2 1
1 2 3
3 3
1 2 5
2 3 5
3 1 2
0 0
输出样例#:
3
2
题目来源:
DreamJudge 1565

题目解析:最短路径的模板题,直接使用最短路径模板算法即可。

 

参考代码(通用模板)

/* 
spfa + vector 
SPFA可以有负边权、可以用一点个入队是否超过N次判断是否存在负环 
*/  
#include <bits/stdc++.h>  
using namespace std;  
  
#define INF 0x3f3f3f3f  
const int maxn = 105;  
int n, m;  
  
struct Edge{  
    int u, v, w;  
    Edge(int u, int v, int w):u(u),v(v),w(w) {}  
};  
  
vector<Edge> edges;  
vector<int> G[maxn];  
int dist[maxn]; // 存放起点到i点的最短距离  
int vis[maxn]; // 标记是否访问过  
int p[maxn]; // 存放路径  
  
void spfa(int s) {  
    queue<int> q;  // 如果这个spfa超时的时候可以把队列改为和dijkstra一样的优先队列
    for (int i = 0; i <= n; i++) dist[i] = INF;  
    dist[s] = 0;  
   ...
登录查看完整内容


课后作业

练习题目

DreamJudge 1344 最短路径问题
DreamJudge 1286 最短路径
DreamJudge 1224 I Wanna Go Home


登录后开始许愿

暂无评论,来抢沙发