跟所有人一样，农夫约翰以着宁教我负天下牛，休叫天下牛负我的伟大精神，日日夜夜苦思生 财之道。为了发财，他设置了一系列的规章制度，使得任何一只奶牛在农场中的道路行走，都 要向农夫约翰上交过路费。 农场中由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
输入输出样例
5 7 2
2
5
3
3
4
1 2 3
1 3 2
2 5 3
5 3 1
5 4 1
2 4 3
3 4 4
1 4
2 3
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]);
}
}