SPFA

最短路

同样是解决单源最短路径问题的算法，只不过这个算法可以处理负边权问题。

相对于Dijstra的贪心，这个SPFA算法就要稍微简单一点

首先，我去从起点开始走，每一条边只要是能走并且比之前的路径段的我就入队列。

一直走到不能再走为止，此时每一个点与起点的距离都可以算出来了。

Code

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+12,inf=2147483647;
int n,m,s,cnt;
int dis[N],vis[N],head[N];
struct {
  int to,nex,w;
}edge[N];
void addedge(int u,int v,int w)
{
  ++cnt;
  edge[cnt].nex=head[u];
  edge[cnt].to=v;
  edge[cnt].w=w;
  head[u]=cnt;
}

void spfa(){
  queue<int>q;
  for(int i=1;i<=n;i++)
  {
    dis[i]=inf;
    vis[i]=0;
  }
  q.push(s);dis[s]=0;vis[s]=1;
  while( !q.empty() )
  {
    int x=q.front();
    q.pop();
    vis[x]=0;
    for(int i=head[x];i;i=edge[i].nex)
    {
      int y=edge[i].to;
      if( dis[y]>dis[x]+edge[i].w )
      {
        dis[y]=dis[x]+edge[i].w;
        if( !vis[y] )
        {
          vis[y]=1;
          q.push(y);
        }
      }
    }
  }

}


int main(){
  cin>>n>>m>>s;
  for(int i=1;i<=m;i++)
  {
    int u,v,w;
    cin>>u>>v>>w;
    addedge(u,v,w);
  }
  spfa();
  for(int i=1;i<=n;i++)
    cout<<dis[i]<<" ";




}

最负环

和最短路的求法是很相近的，但只不过我们记录每个节点入队的次数，当入队次数大于了节点各数的时候，就证明从该节点开始走，会沿着某一条路径更新权值，并且当回到该节点的时候，所有边权相加得到的结果为负数，就出现了一个负环。

Code

#include<bits/stdc++.h>
using namespace std;
const int N=6e3+12,inf=1e9+12;
int a[N],head[N],d[N],cnt;
bool vis[N];
int t,u,v,w,n,m;

struct {
  int to,nex,w;
}edge[N];

void addedge(int u,int v,int w)
{
  cnt++;
  edge[cnt]={v,head[u],w};
  head[u]=cnt;
}
queue<int>q;
void spfa()
{

  while(!q.empty()) q.pop();
  a[1]=1;
  d[1]=0;
  vis[1]=1;
  q.push(1);
  while( !q.empty() )
  {
    int y=q.front();
    vis[y]=0;
    q.pop();
    for(int i=head[y];i;i=edge[i].nex)
    {
      int x=edge[i].to;
      if( d[x]>edge[i].w+d[y] )
      {
        d[x]=edge[i].w+d[y];

        if(!vis[x])
        {a[x]++;
         if( a[x]>=n )
        {printf("YES\n");
         return;
        }
        q.push(x);
        vis[x]=1;
        }

      }
    }
  }
  printf("NO\n");

}

int main(){
  scanf("%d",&t);
  while(t--)
  {

    cnt=0;
    scanf("%d %d",&n,&m);
    fill(d+1,d+1+n,inf);
    memset(a,0,sizeof(a));
    memset(vis,0,sizeof(vis));
    memset(head,0,sizeof(head));
    while(m--)
    {
      scanf("%d %d %d",&u,&v,&w);
      addedge(u,v,w);
      if( w>=0 )
        addedge(v,u,w);
    }
    spfa();

  }





}