SPFA模板

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>

using namespace std;

const int maxn=155555;
const int INF=-1;

struct NODE
{
    int to;
    long long w;
    int next;
}link[maxn];

int edge,node,src,dest;
long long dist[maxn];
int head[maxn];
bool visit[maxn];
int outque[maxn];

queue<int>que;

void prepare(int _node,int _src)
{
    node=_node;
    src=_src;
    for (int i=0;i<=node;i++) head[i]=-1;
    edge=0;
}

void addedge(int u,int v,int c)
{
    link[edge].w=c;link[edge].to=v;link[edge].next=head[u];head[u]=edge++;
    link[edge].w=c;link[edge].to=u;link[edge].next=head[v];head[v]=edge++;
}

bool SPFA()
{
    int top;
    for (int i=0;i<=node;i++)
    {
        dist[i]=INF;
    }
    memset(visit,0,sizeof(visit));
    memset(outque,0,sizeof(outque));
    while (!que.empty()) que.pop();
    que.push(src);
    visit[src]=true;
    dist[src]=0;
    while (!que.empty())
    {
        top=que.front();
        que.pop();
        visit[top]=false;
        outque[top]++;
        if (outque[top]>node) return false;
        int k=head[top];
        while (k!=-1)
        {
            if ( dist[link[k].to]==INF||dist[link[k].to]>dist[top]+link[k].w )
            {
                dist[link[k].to]=dist[top]+link[k].w;
                if (!visit[link[k].to])
                {
                    visit[link[k].to]=true;
                    que.push(link[k].to);
                }
            }
            k=link[k].next;
        }
    }
    return true;
}

----------------------------------------------------------------------------------------------------

新的模板

#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>

using namespace std;

const int maxn=1111;
const int maxm=111111;
const int INF=1e9;

struct EDGE
{
    int to;
    int w;
    int next;
}edges[maxm];

int node,src,dest,edge;
int head[maxn],dist[maxn];

void prepare(int _node,int _src=0,int _dest=0)
{
    node=_node,src=_src,dest=_dest;
    for (int i=0; i<=node; i++) head[i]=-1;
    edge=0;
}

void addedge(int u,int v,int c)
{
    edges[edge].w=c,edges[edge].to=v,edges[edge].next=head[u],head[u]=edge++;
    edges[edge].w=c,edges[edge].to=u,edges[edge].next=head[v],head[v]=edge++;
}

bool spfa(int node,int src,int head[],EDGE edges[],int dist[])
{
    int i,l,r,u,v,w;
    bool visit[maxn];
    int q[maxn],outque[maxn];
    memset(visit,0,sizeof(visit));
    memset(outque,0,sizeof(outque));
    for (int i=0; i<=node; i++) dist[i]=INF;
    r=0;
    q[r++]=src;
    dist[src]=0;
    visit[src]=true;
    for (l=0; l!=r; ( (++l>=maxn)?(l=0):(1) ))
    {
        u=q[l];
        visit[u]=false;
        outque[u]++;
        if (outque[u]>node) return false;
        for (i=head[u]; i!=-1; i=edges[i].next)
        {
            v=edges[i].to;
            w=edges[i].w;
            if (dist[u]+w<dist[v])
            {
                dist[v]=dist[u]+w;
                if (visit[v]) continue;
                q[r++]=v;
                visit[v]=true;
                if (r>=maxn) r=0;
            }
        }
    }
    return true;
}