堆优化dijkstra求调
查看原帖
堆优化dijkstra求调
690561
违规用户名690561楼主2023/5/24 23:05

解答者,蒟蒻将送上关注

本地CE,实在看不出来 另外请大佬帮我看看代码逻辑有无问题,堆优化掌握的不太扎实,谢谢。

#include<bits/stdc++.h>
using namespace std;
const int INF = 0x7fffffff;
int n, m, s, t, dis[200], s1, s2, s3;
bool vis[200];
struct Y {
	int t1, t2;//t1为点,t2为距离
};
vector<Y> v[200];//v[u]是和点u联通的所有点的集合;
priority_queue<Y, vector<Y>, greater<Y>> q;////优先队列(小根堆),意义同上
void dijkstra() {
	for(int i = 1; i <= n; i++) {
		dis[i] = INF;
	}
	dis[s] = 0;//dis为最短距离
	q.push({s, 0});
	while(!q.empty()) {
		t = q.top().t1;
		q.pop();
		if(vis[t]) continue;//如果已经查过了,就跳过
		vis[t] = true;//标记是否查过
		for(auto i : v[t]) {//遍历所有能到达点t的点
			if(dis[i.t1] > dis[t] + i.t2) {
				//i.t1为点的编号
				//i.t2表示点i到t的距离
				dis[i.t1] = dis[t] + i.t2;
				q.push({i.t1, dis[i.t1]});
			}
		}
	}
}
int main() {
	scanf("%d %d %d", &n, &m, &s);
	for(int i = 1; i <= m; i++) {
		scanf("%d %d %d", &s1, &s2, &s3);
		v[s1].push_back({s2, s3});//建双向边
		v[s2].push_back({s1, s3});
	}
	dijkstra();
	for(int i = 1; i <= n; i++) {
		printf("%d ",dis[i]);
	}
	return 0;
}
2023/5/24 23:05
加载中...