♻️lzhh_lzhh32 • 3个月前
/*
Dijkstra算法
1.欲求节点(本题中的s),贪心
2.找目前点到s的距离最小值
3.更新其它点到S的距离,为原有到s最短距离和经新确定点中转到s的距离两者较小值
*/
#include<iostream>
#include<vector>
#include<cstring>
using namespace std;
int n,m,s;
struct edge{
int to; //去往节点
int len; //边权值
};
vector<edge> map[1005]; //用邻接表存
int dis[1005]; //存储某点到s的距离
bool vis[1005]; //某点是否已更新到s的最短距离
int main(){
cin>>n>>m>>s; //n点,m边,s出发
for(int i=0;i<m;i++){
int from;
edge p;
cin>>from>>p.to>>p.len;
map[from].push_back(p);
}
memset(dis,0x3f,sizeof dis);
vis[s]=true;
for(int i=0;i<map[s].size();i++){ //s能直接到达的点
dis[map[s][i].to]=min(dis[map[s][i].to],map[s][i].len);
}
for(int i=0;i<n-1;i++){ //每次加入一个点,需加n-1次
int minpoint=s;
for(int j=1;j<=n;j++){
if(dis[j]<dis[minpoint]&&!vis[j]) minpoint=j;
//从未确定的点中选出
}
vis[minpoint]=true; //标记为已确定的最短路
for(int j=0;j<map[minpoint].size();j++){
if(!vis[map[minpoint][j].to]){
dis[map[minpoint][j].to]=min(dis[map[minpoint][j].to],dis[minpoint]+map[minpoint][j].len);
} //其它点经过此点中转可能更短
}
}
dis[s]=0;
for(int i=1;i<=n;i++){
if(dis[i]>114514) dis[i]=-1;
cout<<dis[i]<<' ';
}
return 0;
}
评论:
请先登录,才能进行评论