题解

#include <bits/stdc++.h>
using namespace std;
const int M = 1005;
int e[M][M];
int dis[M],vis[M]; 

void dij(int n,int s){
	for(int i=0;i<=n;i++)
		dis[i] = 1e9;
	dis[s] = 0;
	for(int i=1;i<=n;i++){
		int u = 0;
		for(int j=1;j<=n;j++){
			if(!vis[j] && dis[j] < dis[u]) u = j;
		}
		vis[u] = 1;
		for(int j=1;j<=n;j++){
			if(e[u][j]){
				int v = j;
				int w = e[u][j];
				if(dis[v] > dis[u] + w){
					dis[v] = dis[u] + w;
				}
			}	
		}
	}		
}

int main(){
	int n,m,s;
	cin >> n >> m >> s;
	for(int i=0;i<m;i++){
		int u,v,w;
		cin >> u >> v >> w;
		int tmp = e[u][v]?e[u][v]:1e9;
		e[u][v] = min(tmp,w);
	} 
	dij(n,s);
	for(int i = 1;i <= n;i++){
        if(dis[i] != 1e9) cout << dis[i] << ' ';
        else cout << -1 << ' ';
    }
	return 0;
}