最短路径问题-------Dijkstra算法

定义：

Dijkstra(迪杰斯特拉)算法是计算单源最短路径算法，用于计算一个结点到其他所有结点的最短路径。该算法以源点为起始点，不断更新其他点到已经确定距离结点的距离，选取距离最小的结点加入S集合，直到S集合存放有所有的结点。

时间复杂度为O（n2） 

例：

I - 单源最短路径（弱化版）

Background

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

Description

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

Input

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

接下来 mm 行每行包含三个整数 u,v,wu,v,w，表示一条 u→vu→v 的，长度为 ww 的边。

Output

输出一行 nn 个整数，第 ii 个表示 ss 到第 ii 个点的最短路径，若不能到达则输出 231−1231−1。

Sample 1

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

0 2 4 3

Hint

【数据范围】
对于 20%20% 的数据：1≤n≤51≤n≤5，1≤m≤151≤m≤15；
对于 40%40% 的数据：1≤n≤1001≤n≤100，1≤m≤1041≤m≤104；
对于 70%70% 的数据：1≤n≤10001≤n≤1000，1≤m≤1051≤m≤105；
对于 100%100% 的数据：1≤n≤1041≤n≤104，1≤m≤5×1051≤m≤5×105，1≤u,v≤n1≤u,v≤n，w≥0w≥0，∑w<231∑w<231，保证数据随机。

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

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

样例说明：

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

代码：

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#define max 2147483647
unsigned int d[10001],c[10001], n, m, s, u, v, w;
bool b[10001];
struct s {
	int to;
	int next=0;
	unsigned int w;
}a[500001];//链式前向星
int main() {
	int i, j,q,gg,tot=1;
	scanf("%d %d %d", &n, &m, &s);
	for ( i = 0;i < m;i++) {
		scanf("%d %d %d", &u, &v, &w);
		a[tot].to = v;
		a[tot].next = d[u];
		a[tot].w = w;
		d[u] = tot++;
	}//储存边信息
	//初始化c数组（c数组是储存s点到任一点的距离）
	for (int i = 1;i <= n;i++) {
		c[i] = max;
	}
	c[s] = 0;
	for (i = 1;i <= n;i++) {
		q = max;
		for (int j = 1;j <= n;j++) {
			if (b[j] == false && q > c[j])
				q = c[j], gg = j;
		}//找到为访问过的最小值
		if (q == max) {
			break;
		}//剩下的都是不通的，跳过
		b[gg] = true;
		while(d[gg]!=0) {
			c[a[d[gg]].to] = c[a[d[gg]].to] < c[gg] + a[d[gg]].w ? c[a[d[gg]].to] : c[gg] + a[d[gg]].w;
			d[gg] = a[d[gg]].next;
		}//跟新c数组
	}
	for ( i = 1;i <= n;i++) {
		printf("%d ", c[i]);
	}
	return 0;
}