[USACO09DEC]牛收费路径Cow Toll Paths

跟所有人一样，农夫约翰以着宁教我负天下牛，休叫天下牛负我的伟大精神，日日夜夜苦思生财之道。为了发财，他设置了一系列的规章制度，使得任何一只奶牛在农场中的道路行走，都要向农夫约翰上交过路费。农场中由N（1 <= N <= 250）片草地（标号为1到N），并且有M（1 <= M <= 10000）条双向道路连接草地A_j和B_j（1 <= A_j <= N; 1 <= B_j <= N）。

奶牛们从任意一片草地出发可以抵达任意一片的草地。FJ已经在连接A_j和B_j的双向道路上设置一个过路费L_j （1 <= L_j <= 100,000）。可能有多条道路连接相同的两片草地，但是不存在一条道路连接一片草地和这片草地本身。最值得庆幸的是，奶牛从任意一篇草地出发，经过一系列的路径，总是可以抵达其它的任意一片草地。除了贪得无厌，叫兽都不知道该说什么好。

FJ竟然在每片草地上面也设置了一个过路费C_i （1 <= C_i <= 100000）。从一片草地到另外一片草地的费用，是经过的所有道路的过路费之和，加上经过的所有的草地（包括起点和终点）的过路费的最大值。任劳任怨的牛们希望去调查一下她们应该选择那一条路径。

她们要你写一个程序，接受K（1 <= K <= 10,000）个问题并且输出每个询问对应的最小花费。第i个问题包含两个数字s_i 和t_i（1 <= s_i <= N; 1 <= t_i <= N; s_i != t_i），表示起点和终点的草地。

输入输出格式

输入格式：

Line 1: Three space separated integers: N, M, and K
Lines 2..N+1: Line i+1 contains a single integer: C_i
Lines N+2..N+M+1: Line j+N+1 contains three space separated

integers: A_j, B_j, and L_j

Lines N+M+2..N+M+K+1: Line i+N+M+1 specifies query i using two space-separated integers: s_i and t_i

输出格式：

Lines 1..K: Line i contains a single integer which is the lowest cost of any route from s_i to t_i

输入输出样例

输入样例#1：

输出样例#1：

8

9


这道题询问数很多，对于每个询问依次求一遍最短路肯定不行，就算能O（M）求也显然不行，
我们注意到点数N很小，由此想到floyd算法。
但是floyd算法看起来没法解决点权和边权混合的问题，
不过由于floyd算法的一个性质使本题可用floyd算法。
floyd算法最外层循环枚举的是中间点，我们将点按点权从小到大排序，
这样在floyd算法中，对于路径i->k->j，点权最大的点必然是i、j、k中的1个，
然后就能计算出答案了。
时间复杂度：O（N^3）
考试时直接floyed只有30分，但是多做几次floyed就可以AC，但这不是正解，不考虑

 #include<iostream>

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 using namespace std;

 struct zt

 {

     int x,i;

 }c[];

 int n,m,dis[][],cost[][],p[];

 bool cmp(zt a,zt b)

 {

     return a.x<b.x;

 }

 int gi()

 {

     char ch=getchar();

     int x=;

     while (ch<''||ch>'') ch=getchar();

     while (ch>=''&&ch<='')

     {

         x=x*+ch-'';

         ch=getchar();

     }

     return x;

 }

 int main()

 {

     int q,x,y,z,i,j,k;

     cin>>n>>m;

     memset(dis,/,sizeof(dis));

     memset(cost,/,sizeof(cost));

     for (i=; i<=n; i++)

     {

         c[i].x=gi();

         c[i].i=i;

         p[i]=c[i].x;

         dis[i][i]=;

     }

     sort(c+,c+n+,cmp);

     for (i=; i<=m; i++)

     {

         x=gi();

         y=gi();

         z=gi();

         dis[x][y]=min(dis[x][y],z);

         dis[y][x]=dis[x][y];

     }

     for (k=; k<=n; k++)

     {

         for (i=; i<=n; i++)

             {

                 for (j=; j<=n; j++)

                     {

                       dis[i][j]=min(dis[i][c[k].i]+dis[c[k].i][j],dis[i][j]);

                       cost[i][j]=min(cost[i][j],dis[i][c[k].i]+dis[c[k].i][j]+max(p[i],max(p[j],c[k].x)));

                     }

             }

     }

     cin>>q;

     while (q--)

     {

         scanf("%d%d",&x,&y);

         printf("%d\n",cost[x][y]);

     }

 }

lines