疑似问题,a[i].w没有值
by drinktowind @ 2023-09-02 16:44:06
@[drinktowind](/user/719619) 建边看起来没问题,检查一下你的SPFA。
我的建边是设超级源点为n+1,你看看会不会有影响
by ___PatrickChen___ @ 2023-09-02 17:08:37
```
#include <bits/stdc++.h>
using namespace std;
int n,cnt,dis[10010],head[10010],sum[10010];
bool f[10010];
struct node{
int to,next,w;
}a[100010];
queue<int> q;
void add(int u,int v,int w)
{
a[++cnt].to=v;
a[cnt].w=w;
a[cnt].next=head[u];
head[u]=cnt;
}
bool spfa()
{
q.push(0);
while(!q.empty())
{
int x=q.front();
q.pop();
f[x]=0;
for(int i=head[x];i;i=a[i].next)
{
if(dis[a[i].to]>dis[x]+a[i].w)
{
dis[a[i].to]=dis[x]+a[i].w;
if(!f[a[i].to])
{
sum[a[i].to]++;
if(sum[a[i].to]>n+1)
return 0;
f[a[i].to]=1;
q.push(a[i].to);
}
}
}
}
return 1;
}
int main()
{
int n,m,u,v,w;
cin>>n>>m;
for(int i=1;i<=n;i++)
dis[i]=1e9;
f[0]=1;
for(int i=1;i<=n;i++)
add(0,i,0);
for(int i=1;i<=m;i++)
{
cin>>u>>v>>w;
add(v,u,w);
}
if(!spfa())
cout<<"NO";
else{
for(int i=1;i<=n;i++)
cout<<dis[i]<<" ";
}
return 0;
}
```
by drinktowind @ 2023-09-03 09:08:29
27分 @[TianShuiXingHe](/user/723378)
by drinktowind @ 2023-09-03 09:08:52