2019独角兽企业重金招聘Python工程师标准>>> 
Description
Mr. G. 在孟加拉国的一家旅游公司工作。他当前的任务是带一些游客去一些遥远的城市。和所有国家一样，一些城市之间有双向道路。每对相邻城市之间都有一条公交路 线，每条路线都规定了自己的最大乘客数目。Mr. G. 有一份包含城市间道路状况和公交车最大载客量的地图。往往无法一次性地将所有乘客带往目的地。例如，在下面7个城市的地图中，边代表道路，每条边上的数字代表这条道路上公交车的最大载客量。如果Mr. G. 要将99位乘客从城市1带到城市7，则至少要往返5次（他必须陪同每一群乘客）。最佳路线是1-2-4-7。
Input
第 一行为一个整数t，表示测试用例个数。 每组数据的第一行有两个整数N(N≤100)和R(R≤4950)，分别表示城市的数量和道路的数量。接下来的R行每行有3个整数（C1,C2,P），其 中C1和C2为城市编号，P(1<P<10000)是该道路上公交车的最大载客量。各城市编号为1~N的连续整数。第R+1行包含3个整数 （S,D,T），分别表示出发城市，目的城市的编号和游客的数量(1<T<100000)。保证两个城市间最多只有一条道路。
Output
对于每组输入数据，输出最少的往返次数。
Sample Input
1
7 10
1 2 30
1 3 15
1 4 10
2 4 25
2 5 60
3 4 40
3 6 20
4 7 35
5 7 20
6 7 30
1 7 99
Sample Output
5
思路分析：
根据题目给出的信息和例子我们可以看到，从1到7的最优路径是1->2->4->7，其中，最大的运载量取决于这条路径中最小的值，也就是25（2->4）。而且导游要陪同他们一起到达目的地，所以每次最多只能够运送24人，要运99人，就是至少需要跑4趟了。
我们先介绍一个算法，Floyd-Warshall算法。在学习离散数学结构的时候，我们曾经用过这个算法来求传递闭包问题。
我们把刚才说的得到的结果称为最优解。
最优解有三种情况：
１、两点的直达是最优的，比如从1到2,1到3等。
２、两点间只通过一个中间点，得到最优解，如1到5的最优解是60。
３、两点间用通过两各以上的顶点而获得最优解。
对于第一种情况，不需要计算，得到的解是唯一的，也是最优的。
对于第二种情况，使用Floyd算法就是，遍历除了起点和终点的其他所有点，然后看看通过哪一个点得到的结果是最优的（就是通过找所有通过一个点到达终点的边中的最小值）。
对于第三情况，先将所有的点都化简成第二种情况就可以了。
核心代码:
for(k = 0; k < n; k++)
for(i = 0; i < n; i++)
for(j = 0; j <n; j++)
D[i][j] = max(D[i][j], min(D[i][k], D[k][j]));
这是一种动态规划算法，它来源于一个递归的解：
If k==0
dij = wij
else
dij = max(dij(k-1), min(dik(k-1), dkj(k-1)))
按照这种方法自底向上计算出最优解
#include <stdio.h>
const int MAX = 100;
int max(int a, int b) {
return a > b ? a : b;
}
int min(int a, int b) {
return a < b ? a : b;
}
int floyd_warshall(int G[MAX][MAX], int n, int start, int end) {
int D[MAX][MAX];
int i, j, k;
for(i = 0; i < n; i++)
for(j = 0; j < n; j++)
D[i][j] = G[i][j];
for(k = 0; k < n; k++)
for(i = 0; i < n; i++)
for(j = 0; j <n; j++)
D[i][j] = max(D[i][j], min(D[i][k], D[k][j]));
return D[start][end];
}
int main() {
int cases;
int N; // city number
int R; // road number
int C1, C2; // the number of city
int P; // Path
int S; // start city
int E; // destination city
int T; // the numer of visitors
int i, j;
int matrix[MAX][MAX];
int res;
scanf("%d", &cases);
while(cases--) {
scanf("%d %d", &N, &R);
for(i = 0 ; i < N; i++)
for(j = 0; j < N; j++)
matrix[i][j] = 0;
for(i = 0; i < R; i++) {
scanf("%d %d %d", &C1, &C2, &P);
matrix[C1-1][C2-1] = matrix[C2-1][C1-1] = P;
}
scanf("%d %d %d", &S, &E, &T);
res = floyd_warshall(matrix, N, S-1, E-1);
printf("%d\n", T/(res-1) + (T % (res - 1) ? 1 : 0));
}
return 0;
}参考：
《算法导论》：第25章
floy算法应用例子：http://aduni.org/courses/algorithms/courseware/handouts/Reciation_07.html#25504