社区讨论

求助!!!不知道错那。谢谢大佬

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

讨论操作

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

当前回复
1 条
当前快照
1 份
快照标识符
@mi85yg4i
此快照首次捕获于
2025/11/21 09:10
4 个月前
此快照最后确认于
2025/11/21 09:10
4 个月前
查看原帖
CPP
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#define MA 100005
#define Ma 500005
#define inf 0x7fffffff
using namespace std;
int n,m,s;
int fis[MA];
struct node{
	int nex,go,dis;
}e[Ma];
bool vst[MA];
int d[MA];
int cnt;
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 x,int y,int w){
	e[++cnt].nex=fis[x];
	fis[x]=cnt;
	e[cnt].go=y;
	e[cnt].dis=w;
	return ;
}
struct kkk{
	int dis;
	int pos;
	bool operator <( const kkk &x )const
	{
		return x.dis<dis;
	}
};
std::priority_queue<kkk>q;
inline void dijkstra(){
	//memset(vst,false,sizeof(vst));
	//memset(d,0x3f,sizeof(d));
	d[s]=0;
	q.push( (kkk){0,s} );
	while(!q.empty()){
		kkk eg=q.top();
		q.pop();
		int x=eg.pos,ds=eg.dis;
		if(vst[x]){
			continue;
		}
		vst[x]=true;
		for(int i=fis[x];i;i=e[i].nex){
			int y=e[i].go;
			//int z=e[i].dis;
			if(d[y]>d[x]+e[i].dis){
				d[y]=d[x]+e[i].dis;
				if(!vst[y]){
					q.push( (kkk){d[y],y} );
				}
			}
		}
	}
	return ;
}
int main(){
	int i;
	int x,y,w;
	n=read();m=read();s=read();
	for(i=1;i<=m;i++){
		x=read();y=read();w=read();
		add(x,y,w);
		add(y,x,w);
	}
	for(i=1;i<=n;i++){
		d[i]=inf;
	}
	dijkstra();
	for(i=1;i<=n;i++){
		printf("%d ",d[i]);
	}
	return 0;
}

回复

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

正在加载回复...