#include<bits/stdc++.h>
using namespace std;

const int MAXV = 2222; //最大顶点数
const int INF = 1e9;  
int n, m, s; //n点的个数、m有向边的个数、s出发点的编号
int u, v, w; //一条 u →v 的，长度为 w 的边
int G[MAXV][MAXV]; //邻接矩阵
int d[MAXV]; //起点到达各点的最短路径长度 
bool vis[MAXV]; //标记数组，true表示已访问 

void Dijkstra(int s){
	fill(d + 1, d + MAXV, INF); //整个d数组初始化值为INF 
	d[s] = 0; //起点s到自身的距离是0 
	for(int i = 1; i <= n; i++){
		int u = 666, MIN = INF; //先给u随便做个标记 
		for(int j = 1; j <= n; j++){ //找到未访问顶点中最小的d[u]
			if(vis[j] == false && d[j] < MIN){
				u = j;
				MIN = d[j];
			} 
		} 
		//找不到小于INF的d[u]，说明剩下的顶点和起点s不连通
		if(u == 666) return; 
		vis[u] = true; //标记u为已访问 
		for(int v = 1; v <= n; v++){
			//如果v未被访问过且u能到达v且以u为中介点可以使d[v]更优
			if(vis[v] == false && G[u][v] != INF && d[u] + G[u][v] < d[v])
				d[v] = d[u] + G[u][v]; 
		} 
	}
} 

int main(){
	cin >> n >> m >> s;
	fill(G[0], G[0] + MAXV * MAXV, INF); //初始化图G
	for(int i = 1; i <= m; i++){
		cin >> u >> v >> w;
		G[u][v] = w;
	} 
	Dijkstra(s);
	if(u == 666){
		cout << (1 << 31);
	}
	else{
		for(int i = 1; i <= n; i++)
		cout << d[i] << " ";	
	}
	
	return 0;
}

一个样例错了：

In:

5 15 5

2 5 181

1 5 98

4 2 49

3 2 262

4 3 26

2 4 192

5 1 221

2 2 254

4 4 233

1 5 44

5 4 67

4 2 214

1 1 47

1 1 118

5 4 3

正确out:

221 52 29 3 0

我的输出结果：

221 217 29 3 0