社区讨论

谁能告诉我,dijsktar这样写为什么会Wrong?

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

讨论操作

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

当前回复
7 条
当前快照
1 份
快照标识符
@m1yzzoj6
此快照首次捕获于
2024/10/07 20:38
去年
此快照最后确认于
2024/10/07 20:51
去年
查看原帖

众所周知,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>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;
}

回复

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

正在加载回复...