【最短路】洛谷_4779 单源最短路径（标准版）

本文主要是介绍【最短路】洛谷_4779 单源最短路径（标准版），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意

给定一个$N$个点$M$条边的有向图，起点是$S$，求出起点到每个点的最短路

思路

堆优化过后的$dijkstra$算法。

代码

#include<queue>
#include<cstdio>
#include<cstring>
using namespace std;priority_queue< pair<int, int> > Q;struct Edge{int to, v, next;
}e[200001];
int N, M, S, tot;
int head[100001], d[100001], v[100001];void add(int x, int y, int v) {e[++tot].to = y;e[tot].next = head[x];e[tot].v = v;head[x] = tot;
}void dijkstra(int S) {for (int i = 1; i <= N; i++) d[i] = 1073741824;memset(v, 0, sizeof(v));d[S] = 0;Q.push(make_pair(0, S));while (Q.size()) {int x = Q.top().second;Q.pop();if (v[x]) continue;v[x] = 1;for (int i = head[x]; i; i = e[i].next) {int y = e[i].to, z = e[i].v;if (d[y] > d[x] + z) {d[y] = d[x] + z;Q.push(make_pair(-d[y], y));}}}
}int main() {scanf("%d %d %d", &N, &M, &S);int x, y, z;for (int i = 1; i <= M; i++) {scanf("%d %d %d", &x, &y, &z);add(x, y, z);}dijkstra(S);for (int i = 1; i <= N; i++)printf("%d ", d[i]);
}

这篇关于【最短路】洛谷_4779 单源最短路径（标准版）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---