长短代码
2023-08-08 17:02:19
发布于：浙江
4阅读
0回复
0点赞
#include<bits/stdc++.h>
using namespace std;
const int N = 10010,M = 500010;
struct Edge{
int to,dis,last;
}e[M];
int n,m;
int head[N],edge_num,v[N],d[N];
void add_edge(int from,int to,int dis){
edge_num++;
e[edge_num].to = to;
e[edge_num].dis = dis;
e[edge_num].last = head[from];
head[from] = edge_num;
}
void dijkstra(){
memset(d,0x3f,sizeof(d));
d[1] = 0;
for(int i = 1;i <= n;i++){
int t = 0;
for(int j = 1;j <= n;j++){
if(!v[j]){
if(t == 0) t = j;
else if(d[j] < d[t]) t = j;
}
}
v[t] = 1;
for(int j = head[t];j != 0;j = e[j].last){
int to = e[j].to,dis = e[j].dis;
if(!v[to]){
d[to] = min(d[to],d[t] + dis);
}
}
}
}
int main(){
cin>>n>>m;
for(int i = 1;i <= n;i++){
int u,v,w;
cin>>u>>v>>w;
add_edge(u,v,w);
add_edge(v,u,w);
}
dijkstra();
for(int i = 1;i <= n;i++) cout<<d[i]<<" ";
return 0;
}
这里空空如也
有帮助，赞一个