社区讨论

蒟蒻求错

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

讨论操作

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

当前回复
3 条
当前快照
1 份
快照标识符
@mi8616fa
此快照首次捕获于
2025/11/21 09:12
4 个月前
此快照最后确认于
2025/11/21 09:12
4 个月前
查看原帖
CPP
#include<iostream>
#include<cstdio>
#include<queue>
#define inf 0x7fffffff
#define MA 200005
using namespace std;
typedef pair<int,int>pi;
int n,m,s;
int fis[MA*2],nex[MA*2],go[MA*2],d[MA*2],tot;
int dis[MA>>1],vst[MA>>1],top;
pi h[MA*2];
inline int read(){
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();};
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();};
	return x*f;
}
inline void add(int u,int v,int w){
	nex[++tot]=fis[u];
	fis[u]=tot;
	go[tot]=v;
	d[tot]=w;
	return ;
}
inline void dijkstra(int x){
	int i;
	for(i=1;i<=n;i++){
		dis[i]=inf;
		vst[i]=0;
	}
	dis[x]=0;
	vst[x]=1;
	top=0;
	for(i=1;i<=n;i++){
		for(int e=fis[x];e;e=nex[e]){
			int v=go[e];
			if(dis[v]>dis[x]+d[e]){
				dis[v]=dis[x]+d[e];
				h[top++]=pi(-dis[v],v);
				push_heap(h,h+top);
			}
		}
		while(top){
			pi cur=h[0];
			pop_heap(h,h+top);
			--top;
			x=cur.second;
			if(!vst[x]){
				break;
			}
			if(!top){
				return ;
			}
		}
		vst[x]=1;
	}
	return ;
}
int main(){
	int i;
	int x,y,z;
	n=read();m=read();s=read();
	for(i=1;i<=m;i++){
		x=read();y=read();z=read();
		add(x,y,z);
		add(y,x,z);
	}
	dijkstra(s);
	for(i=1;i<=n;i++){
		printf("%d ",dis[i]);
	}
	cout<<inf;
	return 0;
}

回复

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

正在加载回复...