只有60pts

记录详情

代码

#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
int n,m,s,x,y,z;
int dist[1005],G[1005][1005];
bool vis[1005];
void dik(int st){
	memset(dist,0x3f,sizeof(dist));
	dist[st] = 0;
	for (int i = 1;i <= n;i++){
		int id=0;
		for (int j = 1;j <= n;j++)
			if (vis[j] == 0 && dist[j] < dist[id])id = j;
		vis[id] = 1;
		for (int j = 1;j <= n;j++)
			if (G[id][j] != 0)
				dist[j] = min(dist[j] , dist[id]+G[id][j]);
	}
}
int main(){
	cin>>n>>m>>s;
	for(int i=1;i<=m;i++){
		cin>>x>>y>>z;
        if(G[x][y]!=0)G[x][y]=min(G[x][y],z);
		else G[x][y]=z;
	}
	dik(s);
	for(int i=1;i<=n;i++){
        if(dist[i]==0x3f3f3f3f)cout<<(1<<31)-1<<endl;
        else cout<<dist[i]<<" ";
    }
	return 0;
}

验证码祭 ac4j