2023年7月30日发(作者：)

单源最短路模板题⽬描述如题，给出⼀个有向图，请输出从某⼀点出发到所有点的最短路径长度。输⼊格式第⼀⾏包含三个整数 n,m,s分别表⽰点的个数、有向边的个数、出发点的编号。接下来 m⾏每⾏包含三个整数 u,v,w，表⽰⼀条 u→v 的，长度为 w 的边。输出格式输出⼀⾏ n个整数，第 i 个表⽰ s 到第 i个点的最短路径，若不能到达则输出 2^{31}-1。样例输⼊4 6 11 2 22 3 22 4 11 3 53 4 31 4 4输出10 2 4 3spfa⽤dis数组记录源点到有向图上任意⼀点距离，其中源点到⾃⾝距离为0，到其他点距离为INF。将源点⼊队，并重复以下步骤：1. 队⾸x出队2. 遍历所有以队⾸为起点的有向边(x,i)，若dis[x]+w(x,i)#define inf 0x3f3f3f3fusing namespace std;const int N = 1e4 + 10;const int M = 5e5 + 10;struct node { int y, z; int nex;} s[M];int head[N], dist[N];int cnt = 0;bool vis[N];void add(int x, int y, int z) { s[++cnt].y = y, s[cnt].z = z, s[cnt].nex = head[x]; head[x] = cnt;}queue q;void spfa(int st) { memset(dist, inf, sizeof dist); dist[st] = 0; (st); vis[st] = 1; while (!()) { int x = (); (); vis[x] = 0; for (int i = head[x]; i; i = s[i].nex) { int y = s[i].y, z = s[i].z; if (dist[x] + z < dist[y]) { dist[y] = dist[x] + z; if (vis[y] == 0) { (y); vis[y] = 1; } } } }}int main() { ios::sync_with_stdio(false); (0); int n, m, st; int x, y, z; cin >> n >> m >> st; for (int i = 1; i <= m; i++) { cin >> x >> y >> z; add(x, y, z); } spfa(st); for (int i = 1; i <= n; i++) { cout << dist[i] << ' '; } cout << endl; return 0;}dijkstraDijkstra算法适⽤于边权为正的⽆向和有向图，不适⽤于有负边权的图！Dijkstra的⼤致思想就是，根据初始点，挨个的把离初始点最近的点⼀个⼀个找到并加⼊集合，集合中所有的点的d[i]都是该点到初始点最短路径长度，由于后加⼊的点是根据集合S中的点为基础拓展的，所以也能找到最短路径。#include #define inf 0x3f3f3f3fusing namespace std;const int N = 1e4 + 10;const int M = 5e5 + 10;struct node { int y, z; int nex;} s[M];int head[N], dist[N];int cnt = 0;bool vis[N];void add(int x, int y, int z) { s[++cnt].y = y, s[cnt].z = z, s[cnt].nex = head[x]; head[x] = cnt;}priority_queue, vector >, greater > > q;void dijkstra(int st) { memset(dist, inf, sizeof dist); dist[st] = 0; (make_pair(dist[st], st)); while (!()) { int x = ().second; (); if (vis[x])continue; vis[x] = 1; for (int i = head[x]; i; i = s[i].nex) { int y = s[i].y, z = s[i].z; if (dist[x] + z < dist[y]) { dist[y] = dist[x] + z; (make_pair(dist[y], y)); } } }}int main() { ios::sync_with_stdio(false); (0); int n, m, st; int x, y, z; cin >> n >> m >> st; for (int i = 1; i <= m; i++) { cin >> x >> y >> z; add(x, y, z); } dijkstra(st); for (int i = 1; i <= n; i++) { cout << dist[i] << ' '; } cout << endl; return 0;}