最短路（Floyd算法）

题目网址：最短路

最短路径问题使用Floyd算法：（结点编号从1-n）

使用邻接矩阵来保存原图，那么此时邻接矩阵中edge[i][j]的值即表示从结点i和结点j，中间不经过任何结点时距离的最小值（若他们之间有多条边，取最小权值保存在邻接矩阵，也可能是去无穷或者-1，这样来表示不可达）；在图的邻接矩阵表示法中，edge[i][j]表示结点i和结点j中间不经过任何结点时的最短的路径，那么依次为中间允许经过的结点添加结点1，结点2.。。直到添加完这些结点，从结点i到结点j就允许经过所有的结点的最短路径长度就可以确定了，该长度即为由结点i到结点j的最短路径长度。

下面的代码：我自己添加了所经历的路径上的节点的输出，已经注释掉了，有想看的同学把所有注释去掉就可以看到最短路径上经历了哪些节点！

#include<iostream>
#include<algorithm>
using namespace std;
int ans[101][101];
//int path[101][101];//在i到j的路径上的j的前一个节点
//int d[101];//最短路径上经过的节点的编号
const int INF = 100000000;
int main()
{
	int n, m;
	while (cin >> n >> m&&n&&m)
	{
		for (int i = 1; i <= n; i++)
		{
			for (int j = 1; j <= n; j++)
			{
				ans[i][j] = INF;//对邻接矩阵进行初始化，inf代表不可达
				//path[i][j] = -1;
			}
			ans[i][i] = 0;//自己到自己初始化为0
		}
		for (int i = 0; i < m; i++)
		{
			int a, b, c;
			cin >> a >> b >> c;
			ans[a][b] = c;//注意是无向图，所以赋值操作进行两次，关于对角线对称
			ans[b][a] = c;
			//path[a][b] = a;
			//path[b][a] = b;
		}
		for (int k = 1; k <= n; k++)
		{
			for (int i = 1; i < n; i++)
			{
				for (int j = 1; j <= n; j++)
				{
					if (ans[i][j]>ans[i][k] + ans[k][j])
					{
						ans[i][j] = ans[i][k] + ans[k][j];
						//path[i][j] = path[k][j];
					}
				}
			}
		}
		/*int x = n;
		int size = 0;
		d[size++] = n;
		while (path[1][x] != 1)
		{
			x = path[1][x];
			d[size++] = x;
		}
		d[size++] = 1;
		cout << "the shortest path is: " ;
		for (int i = size-1; i >=0; i--)//逆序输出
			cout << d[i] << " " ;
		cout << endl;
		cout << "the shortest spend is: ";*/
		cout << ans[1][n] << endl;
	}
	return 0;
}