之后的题解偏重有用/总结性质，尽量理解算法本身而不是题，时间复杂度什么的也能够放放。

非常久之前做过这个题，当时使用dijkstra做的，关于几个最短路算法，分类的话能够分为下面几种。

1、单源最短路：已知起点（终点），计算从源点到其它各个顶点的最短路径长度。

典型算法：Dijkstra，Bellman-Ford（能够算负的，比較慢），spfa（负权能用，加了松弛操作，速度比較炸天）

2、全局最短路：从一点到还有一点，典型如Floyd，A*启示式算法。

又一次用floyd写一遍：

#include <iomanip>

#include <string.h>

#include <iostream>

using namespace std;

const int INF=0x3f3f3f3f;

int map[305][305];

int path[305][305];

bool visited[10005];

int prev[10005];

int waypoint;

void clearmap()

{

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

    {

        for (int j=0;j<105;j++)

        {

            map[i][j]=INF;

        }

    }

    memset(path,INF,sizeof(path));

    memset(prev,0,sizeof(prev));

    memset(visited,0,sizeof(visited));

}

void floyd()

{

	for(int k=0;k<waypoint;k++)

	{

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

		{

			for(int j=0;j<waypoint;j++)

			{

				if(map[i][k]!=INF && map[k][j]!=INF)

				{

					if(map[i][j]>map[i][k]+map[k][j])

					{

							map[i][j]=map[i][k]+map[k][j];

					path[i][j]=path[k][j];

				}

				}

			}

		}

	}

}

int main()

{

    int route;

    while (cin>>waypoint>>route)

    {

       clearmap();

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

       {

               int a,b,dis;

               cin>>a>>b>>dis;

               if(map[a][b]>dis)

               {

               		map[a][b]=map[b][a]=dis;

               }

       }

       floyd();

        int start,end;

        cin>>start>>end;

        if(start==end)

        {

        	cout<<0<<endl;

        }

        else if(map[start][end]!=INF)

            cout<<map[start][end]<<endl;

        else

            cout<<"-1"<<endl;

    }

    return 0;

}