社区讨论

有没有人帮我康康这个Dijkstra最短路错在哪里

灌水区参与者 3已保存回复 15

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
14 条
当前快照
1 份
快照标识符
@m3wsdft5
此快照首次捕获于
2024/11/25 16:48
去年
此快照最后确认于
2025/11/04 23:28
4 个月前
查看原帖
CPP
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct edge{
	int v;
	ll w;
	edge(int vv,ll ww) {
		v = vv;
		w = ww;
		return;
	}
};
struct node{
	int id;
	ll dis;
	node(int idd,ll diss) {
		id = idd;
		diss = dis;
		return;
	}
	bool operator<(node xx) const{//小根堆 
		return dis > xx.dis;
	}
};
int n,m,s;
vector<edge> g[100010];
ll dis[100010];
bool vis[100010];
priority_queue<node> q;
void Dijkstra() {
	memset(dis,0x3f,sizeof(dis));
	dis[s] = 0;
	q.push(node(s,0));
	while (!q.empty()) {
		node u = q.top();
		q.pop();
		if (vis[u.id]) continue;//
		vis[u.id] = true;//
		for (int i = 0;i < g[u.id].size();i ++) {
			int v = g[u.id][i].v;
			ll w = g[u.id][i].w;
			if (dis[v] > u.dis + w) {
				dis[v] = u.dis + w;
				q.push(node(v,dis[v]));
			}
		}
	}
	return;
}
int main() {
	scanf("%d%d%d",&n,&m,&s);
	for (int i = 1;i <= m;i ++) {
		int ut,vt;
		ll wt;
		scanf("%d%d%lld",&ut,&vt,&wt);
		g[ut].push_back(edge(vt,wt));
	}
	Dijkstra();
	for (int i = 1;i <= n;i ++)
		if (dis[i] == 0x3f3f3f3f3f3f3f3fll) printf("2147483647 ");
		else printf("%lld ",dis[i]);
	printf("\n");
	return 0;
}

回复

15 条回复,欢迎继续交流。

正在加载回复...