社区讨论

为什么会这样?

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

讨论操作

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

当前回复
5 条
当前快照
1 份
快照标识符
@mi7ctfbd
此快照首次捕获于
2025/11/20 19:34
4 个月前
此快照最后确认于
2025/11/20 19:34
4 个月前
查看原帖
我写了个spfa和dijkstra,照理讲我spfa写的比dj熟练,结果我spfa炸了,dj没炸?
CPP
#include <bits/stdc++.h>
#define ll long long
#define reg register
#define maxl 100005
using namespace std;
struct E{
	int to,next;
	ll val;
}edge[maxl<<1];
int head[maxl],vis[maxl],tot,n,m,s;
ll dis[maxl];
queue<int> q;
priority_queue< pair<ll,int> >que;
inline int read()
{
	int ans=0,f=1;char c=getchar();
	while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
	while(isdigit(c)){ans=ans*10+(c-'0');c=getchar();}
	return ans*f;
}
void add(int x,int y,ll v)
{
	edge[++tot].to=y;edge[tot].val=v;edge[tot].next=head[x];head[x]=tot;
}
inline void spfa()
{
	for(reg int i=1;i<=n;i++)dis[i]=0x7ffffffff;
	memset(vis,0,sizeof(vis));
	dis[s]=0,vis[s]=1;
	q.push(s);
	while(q.size()){
		int x=q.front();q.pop();
		vis[x]=0;
		for(reg int i=head[x];i;i=edge[i].next){
			int y=edge[i].to;ll v=edge[i].val;
			if(dis[y]>dis[x]+v){
				dis[y]=dis[x]+v;
				if(!vis[y]){q.push(y);vis[y]=1;}
			}
		}
	}
}
inline void dijstra()
{
	for(reg int i=1;i<=n;i++)dis[i]=0x7ffffffff;
	memset(vis,0,sizeof(vis));
	dis[s]=0;
	que.push(make_pair(0,s));
	while(que.size()){
		int x=que.top().second;que.pop();
		if(vis[x])continue;
		vis[x]=1;
		for(reg int i=head[x];i;i=edge[i].next){
			int y=edge[i].to;ll v=edge[i].val;
			if(dis[y]>dis[x]+v){
				dis[y]=dis[x]+v;
				que.push(make_pair(-dis[y],y));
			}
		}
	}
}
int main()
{
	n=read();m=read();s=read();
	for(reg int i=1;i<=m;i++){
		int u=read(),v=read();ll w=(ll)(read());
		add(u,v,w);
	}
	spfa();
	//dijstra();
	for(reg int i=1;i<=n;i++)printf("%lld ",dis[i]);
	return 0;
}

回复

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

正在加载回复...