最短路之SPFA模板

int d[MAXN],vis[MAXN],w[MAXN][MAXN];
int n;
void SPFA(int s)
{
fill(d,d+n,INF);
d[s]=0;
queue<int> q;
q.push(s);
while(!q.empty())
{
int u=q.front();
q.pop();
for(int v=0; v<n; v++)
{
if(d[v]>d[u]+w[u][v])
{
d[v]=d[u]+w[u][v];
q.push(v);

}
}
}
}

const int inf = 0x3f3f3f3f;
int v[M],w[M],next[M],head[N],d[N],e;//head初始化为⑴，摹拟邻接表
void addedge(int a,int b,int x)//主要如果是无向图的话,每条边要履行两次这个，a,b反过来就行
{
v[e]=b;
w[e]=x;
next[e]=head[a];
head[a]=e++;
}

void SPFA(int s)
{
queue<int> q;
d[s]=0;
q.push(s);
while(!q.empty())
{
int u = q.front();
q.pop();
for(int i=head[u]; i!=⑴; i=next[i])
{
if(d[v[i]]>d[u]+w[i])
{
d[v[i]]=d[u]+w[i];
q.push(v[i]);
}
}
}
}

for(int i=0; i<m; i++)//输入1条带权值的无向边
{
cin>>a>>b>>x;
addedge(a,b,x);
addedge(b,a,x);
}

struct Edge
{
int to,w,next;
}E[maxn];

void init()
{
memset(head,⑴,sizeof(head));
fill(d,d+n,INF);
size = 0;
}

void addedge(int u,int v,int x)
{
E[size].to = v;
E[size].w = x;
E[size].next = head[u];
head[u] = size++;
}

void SPFA(int s)
{
queue<int> q;
d[s]=0;
q.push(s);
while(!q.empty())
{
int u = q.front();
q.pop();
for(int i=head[u]; i!=⑴; i=E[i].next)
{
if(d[E[i].to] > d[u] + E[i].w)
{
d[E[i].to] = d[u]+E[i].w;
q.push(E[i].to);
}
}
}
}