社区讨论

求助Dijkstra,WA五个点

P4779【模板】单源最短路径(标准版)参与者 2已保存回复 2

讨论操作

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

当前回复
2 条
当前快照
1 份
快照标识符
@lo8oyo4g
此快照首次捕获于
2023/10/27 22:11
2 年前
此快照最后确认于
2023/10/27 22:11
2 年前
查看原帖
CPP
#include<bits/stdc++.h>
#define maxn 500005
using namespace std;
struct Edge{
	int u,v,w,next;
}edge[maxn*2]; 
int n,m,cnt,head[maxn*2];//cnt:表示有多少条边 
void add(int u,int v,int w){
	cnt++;
	edge[cnt].u=u;
	edge[cnt].v=v;
	edge[cnt].w=w;
	edge[cnt].next=head[u];
	head[u]=cnt;
}
int dis[maxn],vis[maxn],s=1; //vis[s]=1,表示s是黄点 
struct qnode{
	int v,length;//s---v的长度 	
	bool operator <(const qnode &r) const{
		return r.length<length;
	}
}; 

void dijkstra(){//m*logn
//	memset(dis,0x7fffffff,sizeof(dis));
	dis[s]=0;
	priority_queue<qnode> que;//元素:点的编号,和到s的值
	que.push((qnode){s,0});
	//找到入伙的点,用改点去更新其他的dis值 
	while(!que.empty()){
		qnode temp=que.top();//就是距离最短的值 logn
		que.pop(); 
		int u=temp.v;
		if(vis[u]) continue;
		vis[u]=1;
		for(int i=head[u];i;i=edge[i].next){
			//更新相应的s到其他点的最小值 
			int v=edge[i].v;//v==3
			if(vis[v]==0&&dis[v]>dis[u]+edge[i].w){
				dis[v]=dis[u]+edge[i].w;
				que.push( (qnode){v,dis[v]} );
			}			
		}	
	}
} 
int main(){
	cin>>n>>m>>s;
	for(int i = 1; i <= n; ++i)dis[i] = 0x3f3f3f3f;
	for(int i=1;i<=m;i++){
		int u,v,w;
		cin>>u>>v>>w;
		add(u,v,w);
		add(v,u,w);
	}
	dijkstra(); 
	for(int i=1;i<=n;i++){
		if(dis[i]==0x3f3f3f3f)
			cout<<-1<<' ';
		else
			cout<<dis[i]<<' ';
	}
		
		
	return 0;
}

回复

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

正在加载回复...