spfa---模板

spfa模板

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<queue>
using namespace std;
#define V 1010  //点的个数
#define E 4020  //变的个数*2(双向边)
#define INF 0x3f3f3f3f

struct node
{
	int a,b,len;
}p[E];
int nex[E];
int first[V],f[V],dis[V];
int n,m,ans;

void spfa()
{
	int i;
	queue<int> q;
	for(i=0;i<=n;i++)
	{
		dis[i]=INF;
		f[i]=0;
	}
	dis[1]=0;
	f[1]=1;
	q.push(1);
	while(!q.empty())
	{
		int t=q.front();
		q.pop();
		for(i=first[t];i!=-1;i=nex[i])
		{
			if(dis[t]+p[i].len < dis[p[i].b])
			{
				dis[p[i].b]=dis[t]+p[i].len;
				if(f[p[i].b]==0)
				{
					q.push(p[i].b);
					f[p[i].b]=1;
				}
			}
		}
		f[t]=0;
	}
}
void addedge(int a,int b,int c)
{
	p[ans].a=a;
	p[ans].b=b;
	p[ans].len=c;
	nex[ans]=first[a];
	first[a]=ans;
	ans++;
}
int main()
{
	int i,j,k;
	scanf("%d%d",&n,&m);//n个点，m条边
	memset(first,-1,sizeof(first));
	ans=0;
	while(m--)
	{
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		addedge(a,b,c);
		addedge(b,a,c); //双向边
	}
	spfa();
	printf("%d\n",dis[n]);
	system("pause");
}