本题链接：点击打开链接

本题大意：

首先输入一个n,m。代表有n个点。m条边。然后输入m条边，每条边输入两个点及边权。1为起点，n为终点。输入两个零表示结束。

解题思路：

本题能够使用SPFA算法来做。此算法与dijkstra算法的差别在于，此算法能够计算边权为负值的情况。使用此算法首先须要用邻接表建图，用dis数组存放当前点距起点的最短权值之和。用mark数组标记已使用过的点。SPFA算法过程与广度优先搜索相似，此代码与BFS的差别在于已经标记的点。在再次取出来的时候要取消标记。

本题AC代码例如以下：

#include<stdio.h>

#include<string.h>

#include<queue>

#define MAXN 110

#define MAXM 20200

#define INF 0x3f3f3f3f

using namespace std;

int head[MAXN];

int mark[MAXN];

int dis[MAXN];

int num;

struct node{

	int from;

	int to;

	int val;

	int next;

};

node edge[MAXM];

void getmap(int u,int v,int w)

{

	node e={u,v,w,head[u]};

	edge[num]=e;

	head[u]=num++;

}

void SPFA(int s)

{

	memset(mark,0,sizeof(mark));

	memset(dis,INF,sizeof(dis));

	queue<int>q;

	q.push(s);

	dis[s]=0;

	mark[s]=1;

	while(!q.empty())

	{

		int top=q.front();

		q.pop();

		mark[top]=0;

		for(int i=head[top];i!=-1;i=edge[i].next)

		{

			int u=edge[i].to;

			if(dis[u]>dis[top]+edge[i].val)

			{

				dis[u]=dis[top]+edge[i].val;

				if(!mark[u])

				{

					mark[u]=1;

					q.push(u);

				}

			}

		}

	}

}

int main()

{

	int n,m;

	while(scanf("%d%d",&n,&m),n||m)

	{

		memset(head,-1,sizeof(head));

		num=0;

		for(int i=0;i<m;i++)

		{

			int a,b,d;

			scanf("%d%d%d",&a,&b,&d);

			getmap(a,b,d);

			getmap(b,a,d);

		}

		SPFA(1);

		printf("%d\n",dis[n]);

	}

	return 0;

}