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