主要是dij和链式前向星，代码：

#include<bits/stdc++.h>
using namespace std;
int n, m, s, sum = 0;
struct node {    //创建链式前向星
	int to, next, weight;
}a[200000];
int head[10000];
int dis[10000], t[10000];
void add(int x, int y, int z) {    //增加线段
	a[sum].next = head[x];
	a[sum].to = y;
	a[sum].weight = z;
	head[x] = sum;
	sum++;
}
void dij() {    //dijstra主体代码
	for (int i = 1; i <= n; i++) {
		int minn = 2147483647, zhuan;
		for (int j = 1; j <= n; j++) {
			if (minn > dis[j] && t[j] == 0) {
				minn = dis[j];
				zhuan = j;
			}
		}
		t[zhuan] = 1;
		int lin = head[zhuan];
		while (1) {
			if (lin == -1) {
				break;
			} else {
				dis[a[lin].to] = min(dis[a[lin].to], a[lin].weight + minn);
				lin = a[lin].next;
			}
		}
	}
}
int _in() {
	cin >> n >> m >> s;
	for (int i = 1; i <= n; i++) {
		head[i] = -1;
		dis[i] = 2147483647;
	}
	dis[s] = 0;
	for (int i = 1; i <= m; i++) {
		int x, y, z;
		cin >> x >> y >> z;
		if (x == y)
			continue;
		add(x, y, z);
	}
	dij();
	return 0;
}
int main() {
	_in();
	for (int i = 1; i <= n; i++) {
		if (i == s) {
			cout << 0 << ' ';
		} else {
			cout << dis[i] << ' ';
		}
	}
	return 0;
}

弱化版那题可以AC，这道题零分！！！