【洛谷 P3371】【模板】单源最短路径（弱化版）题解（带权有向图+单源最短路+Dijkstra算法+链式前向星）

【模板】单源最短路径（弱化版）

题目背景

本题测试数据为随机数据，在考试中可能会出现构造数据让SPFA不通过，如有需要请移步 P4779。

题目描述

如题，给出一个有向图，请输出从某一点出发到所有点的最短路径长度。

输入格式

第一行包含三个整数 $n,m,s$，分别表示点的个数、有向边的个数、出发点的编号。

接下来 $m$ 行每行包含三个整数 $u,v,w$，表示一条 $u\to v$ 的，长度为 $w$ 的边。

输出格式

输出一行 $n$ 个整数，第 $i$ 个表示 $s$ 到第 $i$ 个点的最短路径，若不能到达则输出 $2^{31}-1$。

样例 #1

样例输入 #1

4 6 1
1 2 2
2 3 2
2 4 1
1 3 5
3 4 3
1 4 4

样例输出 #1

0 2 4 3

提示

【数据范围】
对于 $20\%$ 的数据：$1\le n\le 5$，$1\le m\le 15$；
对于 $40\%$ 的数据：$1\le n\le 100$，$1\le m\le 10^4$；
对于 $70\%$ 的数据：$1\le n\le 1000$，$1\le m\le 10^5$；
对于 $100\%$ 的数据：$1\le n\le 10^4$，$1\le m\le 5\times 10^5$，$1\le u,v\le n$，$w\ge 0$，$\sum w<2^{31}$，保证数据随机。

Update 2022/07/29：两个点之间可能有多条边，敬请注意。

对于真正 $100\%$ 的数据，请移步 P4779。请注意，该题与本题数据范围略有不同。

样例说明：

图片1到3和1到4的文字位置调换

思路

添加边时要注意，两个点之间可能有多条边。

首先检查从节点 u 出发的所有边，如果已经存在一条到节点 v 的边，那么就更新这条边的权重为 w 和原来权重的较小值，然后返回。

如果不存在从节点 u 到节点 v 的边，那么就在 edge 数组中创建一条新的边，并将这条边的权重设置为 w，结束节点设置为 v，下一个节点设置为 head[u]。然后，更新 head[u] 为新创建的边的索引，并增加 cnt 的值。

使用Dijkstra算法，求解单源最短路径问题。

首先，重置访问标记，设置所有节点未访问，并将所有节点的前驱节点初始化为-1。然后，将所有节点到源节点的距离初始化为无穷大。对于源节点的所有相邻节点，更新它们到源节点的距离，并设置它们的前驱节点为源节点。接着，将源节点的距离设置为0，并标记源节点已访问。

接下来，进行n次循环。在每次循环中，找出未访问的节点中到源节点距离最短的节点，并将其标记为已访问。然后，更新这个节点的所有相邻节点的距离。如果新的距离比原来的短，就更新距离，并设置前驱节点为当前节点。这个过程会一直进行，直到所有节点都被访问或者找不到未访问的节点到源节点的距离小于无穷大。

注意

1. 两个点之间可能有多条边，在插入边时检查是否存在多条边连接同一对节点。
2. 用邻接矩阵存储图，部分测试点会报MLE。这里使用链式前向星存储图。

AC代码

#include <algorithm>
#include <bitset>
#include <cstring>
#include <iostream>
#define AUTHOR "HEX9CF"
using namespace std;
using ll = long long;

const int N = 1e6 + 7;
const int INF = (1 << 31) - 1;

struct Node {
	int w, to, next;
} edge[N];
int head[N];
int cnt = 0;

// 点的个数、有向边的个数、出发点的编号
int n, m, s;
// 最短路径长度
int dist[N];
// 前驱节点
int prior[N];
bitset<N> vis;

void add(int u, int v, int w) {
	// 两个点之间可能有多条边
	for (int i = head[u]; ~i; i = edge[i].next) {
		if (edge[i].to == v) {
			edge[i].w = min(edge[i].w, w);
			return;
		}
	}
	edge[cnt] = {w, v, head[u]};
	head[u] = cnt++;
}

void dijkstra() {
	vis.reset();
	memset(prior, -1, sizeof(prior));
	for (int i = 1; i <= n; i++) {
		dist[i] = INF;
	}
	for (int i = head[s]; ~i; i = edge[i].next) {
		int to = edge[i].to;
		// 节点i与出发点s相邻
		prior[to] = s;
		// 初始化出发点s到i点的最短路径长度
		dist[to] = edge[i].w;
	}

	dist[s] = 0;
	vis[s] = 1;
	for (int i = 1; i <= n; i++) {
		int dmin = INF;
		int t = s;
		// 寻找距离出发点s最近的节点t
		for (int j = 1; j <= n; j++) {
			if (!vis[j] && dist[j] < dmin) {
				t = j;
				dmin = dist[j];
			}
		}
		if (t == s) {
			// 找不到最近的节点t
			return;
		}
		// 加入集合
		vis[t] = 1;
		// 更新t点的邻接点到出发点的距离
		for (int j = head[t]; ~j; j = edge[j].next) {
			int to = edge[j].to;
			if (!vis[to] && dist[to] > (dist[t] + edge[j].w)) {
				dist[to] = dist[t] + edge[j].w;
				prior[to] = t;
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	memset(head, -1, sizeof(head));

	cin >> n >> m >> s;
	for (int i = 1; i <= m; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		add(u, v, w);
	}
	dijkstra();
	for (int i = 1; i <= n; i++) {
		cout << dist[i] << " ";
	}
	cout << "\n";
	return 0;
}