社区讨论
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 条回复,欢迎继续交流。
正在加载回复...