最短路

原题链接：https://acm.dingbacode.com/showproblem.php?pid=2544

Problem Description：

众所周知，小明的体能非常的差。体能弱弱的小明发现他每次背着电脑在教学楼和寝室来回走的路实在是太累了，所以他想找到一条他最短的路在两处往返来让他轻松一点

Input：

输入包括多组数据。每组数据第一行是两个整数N、M（N<=100，M<=10000），N表示在去教学楼的路上有几个路口，标号为1的路口是寝室门口所在地，标号为N的路口是教学楼所在地，M则表示在寝室和教学楼之间有几条路。N=M=0表示输入结束。接下来M行，每行包括3个整数A，B，C（1<=A,B<=N,1<=C<=1000）,表示在路口A与路口B之间有一条路，我们的小明走这条路需要花C的时间。
输入保证至少存在1条寝室到教学楼的路线。

Output：

对于每组输入，输出一行，表示小明走到教室的最短时间

Sample Input：

2 1
1 2 3
3 3
1 2 5
2 3 5
3 1 2
0 0

Sample Output：

3
2

解题思路：

Dijstra算法

AC代码：

#include
#include
#include
#define maxn 1050
#define maxdistance 0x3f3f3f
using namespace std;
int N, M;							//N为结点总数，M为边数
int e[maxn][maxn];						//存图
int dis[maxn];							//起点到其他点的最短距离
int flag[maxn];
int dijstra()
{
	memset(dis, maxdistance, sizeof(dis));
	memset(flag, 0, sizeof(flag));
	dis[1] = 0;						//起点到自身的距离为0
	for (int i = 0; i < N; i++)
	{
		int t = -1;
		for (int j = 1; j <= N; j++)
		{
			if (!flag[j] && (t == -1 || dis[t] > dis[j]))
				t = j;
		}
		flag[t] = 1;
		for (int j = 1; j <= N; j++)
		{
			dis[j] = min(dis[j], dis[t] + e[t][j]);
		}
	}
	return dis[N];
}

int main()
{
	while (cin >> N >> M)				        //输入结点总数N，边数M
	{
		memset(e, 0x3f, sizeof(e));
		if (N == 0 && M == 0)	break;
		while (M--)
		{
			int A, B, C;				//A到B的边长度为C
			cin >> A >> B >> C;			//输入边
				e[A][B] = min(e[A][B], C);	//保留最小值进图
				e[B][A] = min(e[B][A], C);
		}
		cout << dijstra() << endl;
	}
	return 0;
}