题意：每个城市举办庆祝有一定的花费，A在路径上会选择庆祝花费最大的城市
让你求，A回家所花的路费和庆祝费最少，也就是说并不是最短路径就是结果，
还有可能就是路费比最短路径的多，但是庆祝费就比它的少，总的加起来可能更小。
思路：枚举每个城市作为庆祝的点，设为x。以x为源点，用dijks求单源路径，路径上如果有大于x庆祝费的点，则不考虑进去。
求完所有点到x的单源路径后，用两重j、k的for循环，同步更新从j到k所需要的最小花费
#include <iostream>
#include <algorithm>
#include <string.h>
#include <string>
#include <cstring>
#include <stdio.h>
#include <map>
#include <vector>
using namespace std;
const int maxn=0x3f3f3f3f; int c,r,q;
int c1,c2,d;
int a,b;
int road[][];
int feast[];
int ans[][];//ans[i][j]即为询问的答案，表示i到j最少的花费
int dis[];//当x为庆祝点时，dis[i]表示以第x城市作为举办宴会的地方，i到x之间的最短路径(即花费);
vector<int> link[];
int vis[];
int cases=;
int blank=; void init(){
for(int i=;i<=c;i++)
link[i].clear();
memset(road,maxn,sizeof(road));
memset(ans,maxn,sizeof(ans));
}
int main()
{
while(scanf("%d%d%d",&c,&r,&q)!=EOF){
if(c== && r== && q==)
break;
//如果不这样，则最后一个case输出完后会多打一个空格，这也给我wrong answer。。。
if(blank)
puts("");
else
blank=;
cases++;
init();
for(int i=;i<=c;i++){
scanf("%d",&feast[i]);
}
for(int i=;i<r;i++){
scanf("%d%d%d",&c1,&c2,&d);
road[c1][c2]=d;
road[c2][c1]=d;
link[c1].push_back(c2);
link[c2].push_back(c1);
} for(int i=;i<=c;i++){ //以i作为庆祝城市，并且以i作为源点，求单源路径
memset(dis,maxn,sizeof(dis));
dis[i]=;
memset(vis,,sizeof(vis)); //循环n次，这里我没用优先级队列
for(int z=;z<=c;z++){
int mincost=maxn;
int idx;
for(int k=;k<=c;k++){
if(vis[k]==){
if(dis[k]<mincost && feast[k]<=feast[i]){
mincost=dis[k];
idx=k;
}
}
}
vis[idx]=;
for(int g=;g<link[idx].size();g++){
int v=link[idx][g];
if(v!=idx){
if(feast[v]<=feast[i] && dis[idx]+road[idx][v]<dis[v]){
dis[v]=dis[idx]+road[idx][v];
}
}
}
} //每次求完以i为庆祝点的单源路径后，与之前比较，更新ans[j][k]的值，
//如果此次，从j到k之间在i点庆祝的花费比之前一次循环中的在i'庆祝的花费要少，则更新
for(int j=;j<=c;j++){
for(int k=;k<=c;k++){
if(feast[i]+dis[j]+dis[k]<ans[j][k]){
ans[j][k]=feast[i]+dis[j]+dis[k];
}
}
} }
printf("Case #%d\n",cases);
for(int i=;i<=q;i++){
scanf("%d%d",&a,&b);
if(ans[a][b]==maxn){
printf("-1\n");
}
else{
printf("%d\n",ans[a][b]);
}
}
//printf("\n"); }
return ;
}