问题简介：
给定T条路，S个起点，D个终点，求最短的起点到终点的距离。
思路简介：
弗洛伊德算法即先以a作为中转点，再以a、b作为中转点，直到所有的点都做过中转点，求得所有点到其他点的最短路径，Floyd算法适用于多源最短路径，是一种动态规划算法，稠密图效果最佳，边权可正可负。优点：容易理解，可以算出任意两个节点之间的最短距离，代码编写简单。缺点：时间复杂度比较高，不适合计算大量数据。Floyd算法时间复杂度为n^3,Dijikstra算法为n^2。
优化代码：
#include <iostream>
#include <cmath>
#include <stdio.h>
#include <cstdio>
#include <cstring>
#include<algorithm>
#include<time.h>
#include<math.h>
#include <stdlib.h>
#include <string.h>
#include <stack> using namespace std; #define MAXN 1000000
#define N 1010
int map[N][N], s[N], e[N], maxx;
int T, S, D;
int floyd()
{
int res = MAXN;
for (int k = ; k <= maxx; k++)
for (int i = ; i <= maxx; i++)
if (map[i][k] != MAXN)//优化
for (int j = ; j <= maxx; j++)
{
if (map[i][j]>map[i][k] + map[k][j])
map[i][j] = map[i][k] + map[k][j];
if (s[i] && e[j] && res>map[i][j])//因为是取最短的一条路径，所以随时记录起点到终点的路
res = map[i][j];
}
return res;
}
int main()
{
while (scanf("%d%d%d", &T, &S, &D) != EOF)
{
memset(map, , sizeof(map));
memset(s, , sizeof(s));
memset(e, , sizeof(e));
for (int i = ; i <= ; i++)//初始化
for (int j = ; j <= ; j++)
map[i][j] = MAXN;
int u, v, w;
for (int i = ; i <= T; i++)
{
scanf("%d%d%d", &u, &v, &w);
maxx = max(maxx, max(u, v));
map[u][v] = w;
}
for (int i = ; i <= S; i++)
{
scanf("%d", &u);
s[u] = ;//起点
}
for (int i = ; i <= D; i++)
{
scanf("%d", &u);
e[u] = ;//终点
}
printf("%d\n", floyd());
}
return ;
}