题解
2025-06-27 21:39:35
发布于:陕西
5阅读
0回复
0点赞
#include<bits/stdc++.h>
using namespace std;
int n,m,s;
int dis[1005];
bool vis[1005];
int mp[1005][1005];
int main()
{
cin>>n>>m>>s;
for(int i=0;i<=n;i++){ //初始化
for(int j=0;j<=n;j++){
mp[i][j]=1e9;
}
}
for(int i=0;i<=n;i++){ //初始化
dis[i]= 1e9 ;
}
memset(vis,0,sizeof(vis));
for(int i=1;i<=m;i++)
{
int u,v,w;
cin>>u>>v>>w;
mp[u][v]=min(mp[u][v],w);
}
dis[s]=0;
for(int j=1;j<n;j++)
{
int mest=0;
for(int i=1;i<=n;i++)
{
if(dis[i]<dis[mest]&&vis[i] == 0)
{
mest=i;
}
}
vis[mest]=1;
for(int i=1;i<=n;i++)
{
dis[i]=min(dis[i],dis[mest]+mp[mest][i]);
}
}
for(int i=1;i<=n;i++)
{
if(dis[i]!=1e9)
{
cout<< dis[i] <<" ";
}
else
{
cout<< -1 <<" ";
}
}
return 0;
}
这里空空如也
有帮助,赞一个