社区讨论

dijsktar这个代码哪里错了?

学术版参与者 6已保存回复 12

讨论操作

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

当前回复
12 条
当前快照
1 份
快照标识符
@m1z0l7wl
此快照首次捕获于
2024/10/07 20:54
去年
此快照最后确认于
2025/11/04 23:59
4 个月前
查看原帖
大佬,谁能帮我康一康,dijsktar这个代码哪里错了?
CPP
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,m,s,dis[100010];
bool flag[100010];
struct node{
	int to,w;
	bool operator>(const node &x)const&{
        return x.w<w;
    }
};
vector<node>a[100010];
priority_queue<node,vector<node>,greater<node> >q;
int main(){
	cin>>n>>m>>s;
	int i,t;
	while(m--){
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		a[x].push_back({y,z});
	}
	memset(dis,0x3f,sizeof(dis));
	q.push({s,0});
	dis[s]=0;
	flag[s]=1;
	while(!q.empty()){
		node tmp=q.top();
		q.pop();
		t=tmp.to;
//		if(flag[t]==0){
//			flag[t]=1;
			for(i=0;i<a[t].size();i++){
				int e=a[t][i].to;
					if(dis[e]>dis[t]+a[t][i].w){
						dis[e]=dis[t]+a[t][i].w;
						if(flag[e]==0){
							q.push({e,dis[e]});
							flag[e]=1;
						}
					}
				}
//		}
	}
	for(i=1;i<=n;i++)cout<<dis[i]<<' ';
	return 0;
}

回复

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

正在加载回复...