最短路 SPFA模板

#include "cstdio"  //邻接表+spfa算法(不断松弛操作) hdu 2544
#include "queue"
#include "string.h"
using namespace std;

struct node 
{
	int x;
	int value;   //价值
	int next;  //存下一条边的下标
}edge[60000];

int n,m,idx;
bool mark[1505];
int dis[1505],adj[1505];

void init()
{
	int i;
	idx = 1;
	memset(mark,false,sizeof(mark));  //标记每个点是否加入了队列
	for(i=2;i<1505;i++)                //存最短距离
		dis[i] = 0x3fffffff;
	dis[1] = 0;
	memset(adj,-1,sizeof(adj));  //建邻接表用，存最开始的边的下标
}

void addedge(int u,int v,int w)
{
	edge[idx].x = v;
	edge[idx].value = w;
	edge[idx].next = adj[u];
	adj[u] = idx;
	idx++;
}

int main()
{
	int i,j;
	int u,v,w;
	while(scanf("%d%d",&n,&m),n||m)  //n表示点的个数，m表示边的条数
	{
		init();   //初始化函数
		for(i=1;i<=m;i++)
		{
			scanf("%d %d %d",&u,&v,&w);
			addedge(u,v,w);
			addedge(v,u,w);
		}
		int cur = 1;
		queue<int> q;
		q.push(cur);
		mark[cur] = true;
		dis[cur] = 0;
		while(!q.empty())
		{
			cur = q.front();
			q.pop();
			mark[cur] = false;  //点已出对列，标记还原；
			int k = adj[cur];
			while(k!=-1)  //对cur连接的边进行遍历
			{
				if(dis[edge[k].x] > dis[cur]+edge[k].value)
				{
					dis[edge[k].x]=dis[cur]+edge[k].value;
					if(mark[edge[k].x]==false)  //若该点还没有加入队列中，则加入队列
					{
						mark[edge[k].x] = true;
						q.push(edge[k].x);
					}
				}
				k = edge[k].next;  //访问下一个点
			}
		}
		printf("%d
",dis[n]);
	}
	return 0;
}