16_lln @ 2024-07-01 14:01:07
#include <bits/stdc++.h>
using namespace std;
int n,m,u;
int d[10005],vis[10005],a[10005][10005]/*,path[10005]*/;
void dijkstra(){
memset(d,0x3f,sizeof(d));
memset(vis,0,sizeof(vis));
d[s]=0;//初始化
for(int i=1;i<n;i++){
int u=0;
for(int j=1;j<=n;j++){
if(!vis[j]&&(u==0||d[j]<d[u])) s=j;//提取x数值
}
vis[u]=1;//标记已访问数值
for(int g=1;g<=n;g++) d[g]=min(d[g],d[u]+a[s][g]);
}
}
int main(){
cin>>n>>m>>s;
memset(a,0x3f,sizeof(a));
for(int i=1;i<=n;i++) a[i][i]=0;//自己与自己的最短路径==0
for(int i=1;i<=m;i++){
int x,y,z;
cin>>x>>y>>z;
a[x][y]=min(a[x][y],z);//判断重复边不同权值
}
dijkstra();//函数
for(int i=1;i<=n;i++) cout<<d[i]<<endl;//输出最短距离
return 0;
}
by gxa33336 @ 2024-07-01 14:08:26
@16_lln ,看一下有没有大佬
by ZMTZHT519 @ 2024-07-01 14:10:30
@hrk_
by danlao @ 2024-07-01 14:21:03
@16_lln 不要用邻接矩阵存,存不下的,a
数组开太大了,用 vector
或链式前向星
by 16_lln @ 2024-07-01 14:22:36
@danlao 谢谢dalao
by hrk_ @ 2024-07-01 14:27:32
@ZMTZHT519 骚扰我,jbl