咖啡

用户名：Tianxn

访问量：138103

签　名：

十年OI一场空，不开LL见祖宗。

等　　级
排　　名	10
经　　验	27291
参赛次数	10
文章发表	197
年　　龄	22
在职情况	学生
学　　校	西安电子科技大学
专　　业	软件工程

　　自我简介：

TA的其他文章

信息学奥赛一本通T1309-回文数-题解（C++代码）
浏览：1324

信息学奥赛一本通T1255-迷宫问题-题解（C++代码）BFS求最短路
浏览：1104

信息学奥赛一本通T1255-迷宫问题-题解（C++代码）DFS求最短路
浏览：440

你可能喜欢

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

C语言程序设计教程（第三版）课后习题7.4 （C++代码）（和输入10个数排序没有区别，直接sort即可）

数据结构-Dijskra(迪杰斯特拉)最短路径算法-题解(邻接表+堆优化)

　　作者: 咖啡　　　　发表时间：2019-06-10 15:19:57 浏览：3929　|　评论：0　

原题链接：数据结构-Dijskra(迪杰斯特拉)最短路径算法

邻接表使用vector容器+pair结合使用，pair相当一个结构体（只有两个元素，自己赋予具体实际意义）pair中不需要重载<运算符，可直接使用。

如果考察最短路径算法，肯定是堆化的Dijskra算法或者SPFA算法，其他效率上不能AC,甚至还需要自己手写堆（卡SPFA的时间）。

相关知识，大家自己查看博客。

这个题我会用SPFA算法写一遍，方便大家学习和查看，谢谢。
代码如下：

```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 9, INF = 0x3f3f3f3f;
vector<pair<int, int> > E[N]; // pair<顶点, 权值>
int n, dis[N], inq[N];

void Dijskra(int s) {
	for(int i = 0; i < n; ++i) dis[i] = (i == s ? 0 : INF);
	priority_queue<pair<int, int> > Q;
	Q.push(make_pair(-dis[s], s)); // 注意first代表距离，second代表点！！！
	while(!Q.empty()) {
		int u = Q.top().second;
		Q.pop();
		if(inq[u]) continue;
		inq[u] = 1;
		for(int i = 0; i < E[u].size(); ++i) {
			int v = E[u][i].first;
			int d = E[u][i].second;
			if(d + dis[u] < dis[v]) {
				dis[v] = d + dis[u];
				Q.push(make_pair(-dis[v], v));
			}
		}
	}
}

int main() {
	int s, tmp;
	scanf("%d%d", &n, &s);
	for(int i = 0; i < n; ++i) {
		for(int j = 0; j < n; ++j) {
			scanf("%d", &tmp);
			if(tmp) E[i].push_back(make_pair(j, tmp));
		}
	}
	Dijskra(s);
	for(int i = 0; i < n; ++i) {
		if(i != s) {
			printf("%d ", (dis[i] == INF ? -1 : dis[i]));
		}
	}
	return 0;
}
```

0.0分

12 人评分

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

咖啡

TA的其他文章

你可能喜欢

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

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

C语言考试练习题_保留字母（C语言代码）

开心的金明（C++代码）

C语言程序设计教程（第三版）课后习题7.4 （C++代码）（和输入10个数排序没有区别，直接sort即可）

数据结构-Dijskra(迪杰斯特拉)最短路径算法-题解(邻接表+堆优化)

评论区

精彩推荐

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

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

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

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

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

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

简单的a+b （C语言代码）

The 3n + 1 problem （C语言代码）

数对（C语言代码）

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

咖啡

TA的其他文章

你可能喜欢

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

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

C语言考试练习题_保留字母 （C语言代码）

开心的金明 （C++代码）

C语言程序设计教程（第三版）课后习题7.4 （C++代码）（和输入10个数排序没有区别，直接sort即可）

数据结构-Dijskra(迪杰斯特拉)最短路径算法-题解(邻接表+堆优化)

评论区

精彩推荐

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

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

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

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

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

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

简单的a+b （C语言代码）

The 3n + 1 problem （C语言代码）

数对 （C语言代码）

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

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

C语言考试练习题_保留字母（C语言代码）

开心的金明（C++代码）

　　评论区

数对（C语言代码）