之后的题解偏重有用/总结性质，尽量理解算法本身而不是题，时间复杂度什么的也能够放放。
非常久之前做过这个题，当时使用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;
}