题解

#include <bits/stdc++.h>
using namespace std;
struct data {
	int p, w;
}; 
int n,m,st,d[10010],vis[10010];
vector<data> v[10010];
void Dijkstra(int x) {
	for (int i = 0;i<=n;i++)
		d[i]= INT_MAX;
	d[x] = 0;
	for (int i = 1;i<=n;i++){
		int u = 0; 
		for (int j = 1;j<=n;j++){
			if(vis[j]==0 && d[j]<d[u])
				u =j;
		}
		vis[u] = 1;
		for (auto item : v[u]){
			if(d[item.p] > d[u] + item.w){
				d[item.p] = d[u] + item.w;
			}
		}
	}
}
int main() {
	cin >>n >>m>>st;
	for (int i = 1;i<=m;i++){
		int x ,y ,z;
		cin >>x  >> y>>z;
		v[x].push_back({y,z});
	}
	Dijkstra(st);
	for(int i=1;i<=n;i++)
		if(d[i]==INT_MAX) cout << "-1 ";
    else cout << d[i] << " ";
	return 0;
}