我也来贡献一份题解:Dijkstra单源最短路径的简单变式【简单C代码】
这道题的前置知识的Dijkstra单源最短路径
算法
如果还没学过,建议去看AcWing算法教程的**图论(2)**中最短路径问题的讲解,u1s1–y总讲的是真的通透!
思路
这道题和单源最短路径唯一的区别就是,多了一个隔离时间,我们可以将所有的隔离时间都加到路径上,也就是直接将问题转化成单源最短路径问题即可~
同时不要忘记所有的路都是双向的,所以在建图的时候,别忘记双向建图,否则没分!
例如:这是题目所给的测试用例
我们可以将它转化为我们熟悉的单源最短路径问题,只要做一个简单的处理即可,然后就可以套用Dijkstra算法的万能模板:
[1] --11-- [2]
| |
8 7
| |
[3] -- 9 -- [4]
让所有的点的 前边 加上这个点的等待时间作为新的 边
代码
#include <iostream>
#include <cstring>
#define int long long
using namespace std;
const int N = 1001;
int g[N][N], dist[N], wait[N]; //g为邻接矩阵
bool st[N]; //表示结点是否已经确定最短路径
int n, m; //n为结点数量,m为边数量
inline void Dijkstra() {
memset(dist, 0x3f, sizeof dist);
dist[1] = 0; //从第一个结点到达第一个结点的最短路径为 0
for (int i = 0; i < n - 1; i++ ) { //循环 n 次处理 n 个结点
int t = -1;
for (int j = 1; j <= n; j++ ) {
if (!st[j] && (t == -1 || dist[j] < dist[t])) { //第一次会选择找到的第一个边然后去找最短的边
t = j; //寻找没有确定最短路径的点当中 到第一个点最近的点
}
}
//找到没有确定的最近的点
for (int j = 1; j <= n; j++) {
dist[j] = min(dist[j], dist[t] + g[t][j]);
}//从第一个最近的点开始向后更新最短路径
st[t] = true; //将确定好最短路径的点设置为true表示已经确定了最短路径
}
cout << dist[n] << endl;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i++ ) {
cin >> wait[i];
}
wait[1] = wait[n] = 0;
memset(g, 0x3f, sizeof g);
for (int i = 0; i < m; i++ ) {
int u, v, c;
cin >> u >> v >> c;
g[u][v] = wait[v] + c; //无重边的情况,如果有重边需要进行取重边的最小值
g[v][u] = wait[u] + c;
}
Dijkstra();
}