本题解在 @ 的这篇题解的基础上将 vector 换成了链式前向星^[1]。

代码（Dijkstra）

#include <bits/stdc++.h>
using namespace std;
// 注意 INF 要设成 2^30-1，否则会爆成负数
const int N = 10005,M = 500005,INF = 1073741823;

// 链式前向星
struct edge{
	int v,w,prev;
	// v：目标点
	// w：边权
	// prev：上一个点
}edges[M];	// 数组存链表
int tail[N],tot;
// tail：指向 i 能到的点的链表的末尾
// tot：edges 最后一个点的下标
void add_edge(int u,int v,int w){
	edges[++tot] = {v,w,NULL};
	edges[tot].prev = tail[u];
	tail[u] = tot;
}

int dis[N],n,m,s;
bool f[N];
void dkstr(){
	for (int i = 1;i <= n;i++){
		int u = -1,mn = INF;
		for (int j = 1;j <= n;j++){
			if (!f[j] && dis[j] < mn){
				u = j;
				mn = dis[j];
			}
		}
		if (u == -1)	return ;
		f[u] = 1;
		for (int j = tail[u];j;j = edges[j].prev){
			int v = edges[j].v,w = edges[j].w;
			if (!f[v])	dis[v] = min(dis[v],dis[u] + w);
		}
	}
}
int main(int argc, char **argv){
	fill(dis,dis + N,INF);
	cin >> n >> m >> s;
	dis[s] = 0;
	for (int i = 0;i < m;i++){
		int u,v,w;
		cin >> u >> v >> w;
		add_edge(u,v,w);
	}
	dkstr();
	for (int i = 1;i <= n;i++){
		if (dis[i] == INF)	printf("%d ",0x7fffffff);
		else	printf("%d ",dis[i]);
	}
	return 0;
}