AC

♻️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;
}

评论:

请先登录,才能进行评论