A569.单源最短路径1（行数最少）

#include <bits/stdc++.h>
using namespace std;
int n,m,s,u,v,w,dis[1005],vis[1005],mp[1005][1005];
void dj(int n,int s){
    memset(vis,0,sizeof vis);
    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[u] > dis[j]) u = j;
        }
        vis[u] = 1;
        for(int j = 1;j <= n;j++){
            if(mp[u][j]){
                dis[j] = min(dis[j],dis[u] + mp[u][j]);
            }
        }
    }
}
int main(int argc, char** argv) {
	cin >> n >> m >> s;
    while(m--){
        int u,v,w;
        cin >> u >> v >> w;
        int tmp = mp[u][v] ? mp[u][v] : 1e9;
		mp[u][v] = min(tmp,w); //浅浅装一下
    }
    dj(n,s);
    for(int i = 1;i <= n;i++){
        if(dis[i] == 1e9) cout << -1 << ' ';
        else cout << dis[i] << ' ';
    }
	return 0;
}