碇真嗣

用户名：dotcpp0690000

访问量：255

签　名：

&quot;HelloWorld&quot;

等　　级
排　　名	2488
经　　验	2282
参赛次数	0
文章发表	3
年　　龄	18
在职情况	学生
学　　校	新疆财经大学
专　　业	计算机科学与技术

　　自我简介：

无

TA的其他文章

C++数组存储三角形简易动态规划版本
浏览：53

我也来贡献一份题解：Dijkstra单源最短路径的简单变式【简单C/C++代码】
浏览：146

你可能喜欢

我也来贡献一份题解：Dijkstra单源最短路径的简单变式【简单C/C++代码】

　　作者: 碇真嗣　　　　发表时间：2024-04-12 00:00:46 浏览：146　|　评论：0　

原题链接：蓝桥杯2022年第十三届决赛真题-出差

# 我也来贡献一份题解：Dijkstra单源最短路径的简单变式【简单C代码】

****

**这道题的前置知识的`Dijkstra单源最短路径`算法**

> 如果还没学过，建议去看**AcWing**算法教程的**图论(2)**中最短路径问题的讲解,u1s1--y总讲的是真的通透！
>
>

## 思路

这道题和单源最短路径唯一的区别就是，多了一个隔离时间，我们可以将所有的隔离时间都加到路径上，也就是直接将问题转化成单源最短路径问题即可~

**同时不要忘记所有的路都是双向的，所以在建图的时候，别忘记双向建图，否则没分！**

例如：这是题目所给的测试用例
![](/image_editor_upload/20240411/20240411115759_52768.png)

我们可以将它转化为我们熟悉的单源最短路径问题，只要做一个简单的处理即可，然后就可以套用**Dijkstra算法**的万能模板：
（第一个点和最后一个点的隔离时间都算作 `0`）
```
[1] --11--  [2]
 |		   |
 8		   3
 |	       |
[3] -- 5 -- [4]
```

> 让所有的点的 **前边** 加上这个点的等待时间作为新的 **边**

## 代码

```c
#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();
} 
```

0.0分

2 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

碇真嗣

TA的其他文章

你可能喜欢

C二级辅导-温度转换（C++代码）

C二级辅导-公约公倍（C语言代码）

蛇行矩阵（C语言代码）

C二级辅导-计负均正（C++代码）

C语言程序设计教程（第三版）课后习题8.7 （C语言代码）

我也来贡献一份题解：Dijkstra单源最短路径的简单变式【简单C/C++代码】

评论区

精彩推荐

上车人数（C语言代码）

高精度加法（C++代码）（大数加法）

WU-小九九（C++代码）

【求[X,Y]内被除3余1并且被除5余3的整数的和】（C语言代码）

printf基础练习2 （C语言代码）

Cylinder （C语言描述+详细分析）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

2003年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

前10名（C语言代码）

C语言程序设计教程（第三版）课后习题5.8 （C语言代码）

碇真嗣

TA的其他文章

你可能喜欢

C二级辅导-温度转换 （C++代码）

C二级辅导-公约公倍 （C语言代码）

蛇行矩阵 （C语言代码）

C二级辅导-计负均正 （C++代码）

C语言程序设计教程（第三版）课后习题8.7 （C语言代码）

我也来贡献一份题解：Dijkstra单源最短路径的简单变式【简单C/C++代码】

评论区

精彩推荐

上车人数 （C语言代码）

高精度加法 （C++代码）（大数加法）

WU-小九九 （C++代码）

【求[X,Y]内被除3余1并且被除5余3的整数的和】 （C语言代码）

printf基础练习2 （C语言代码）

Cylinder （C语言描述+详细分析）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

2003年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

前10名 （C语言代码）

C语言程序设计教程（第三版）课后习题5.8 （C语言代码）

C二级辅导-温度转换（C++代码）

C二级辅导-公约公倍（C语言代码）

蛇行矩阵（C语言代码）

C二级辅导-计负均正（C++代码）

　　评论区

上车人数（C语言代码）

高精度加法（C++代码）（大数加法）

WU-小九九（C++代码）

【求[X,Y]内被除3余1并且被除5余3的整数的和】（C语言代码）

前10名（C语言代码）