这道题是world finals的热身赛第一题。弱菜花了两个小时在做出来-。-
题意：给你一张无向图，然后给若干个查询，问你任意两个定点之间的最短路。最短路的定义是这样的：每个定点有权值，每个边也有权值，最短路等于路径上的所有边权值之和+所有定点的权值最大值。
思路：这道题先分析一下测试数据，顶点最多只有80个边最多有1000条所以一定是有重边的，这道题又要用邻接矩阵存所以输入的时候注意一下就好了，然后看查询有6000+个所以还是会有很多重复的，因此我们就可以想到用floyd来做这道题了。那么定点的权值怎么处理呢？我们想到了floyd的dp过程是按定点顺序的，所以我们将顶点按照花费排个序，这样有序的dp就能解出答案了。
代码如下：
1 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 #include <cmath> 5 #include <cstring> 6 #include <algorithm> 7 #include <queue> 8 #include <stack> 9 #include <vector> 10 #define MP(a, b) make_pair(a, b) 11 #define PB(a) push_back(a) 12 13 using namespace std; 14 15 typedef long long ll; 16 typedef pair<int ,int> pii; 17 typedef pair<unsigned int, unsigned int> puu; 18 typedef pair<int ,double> pid; 19 typedef pair<ll, int> pli; 20 21 const int INF = 0x3f3f3f3f; 22 const double eps = 1e-6; 23 const int LEN = 101; 24 struct V{int tag, val;}; 25 int Map[LEN][LEN], dis[LEN][LEN][LEN], n, m; 26 V vex[LEN]; 27 inline bool cmp(V a, V b){return a.val<b.val;} 28 29 void floyd() 30 { 31 for(int i=1; i<=n; i++){ 32 for(int j=1; j<=n; j++){ 33 dis[i][j][0] = Map[i][j]; 34 if(i==j)dis[i][j][0] = 0; 35 } 36 } 37 for(int x=1; x<=n; x++){ 38 int k = vex[x].tag; 39 for(int i=1; i<=n; i++){ 40 for(int j=1; j<=n; j++){ 41 dis[i][j][x] = min(dis[i][j][x-1], dis[i][k][x-1]+dis[k][j][x-1]); 42 } 43 } 44 } 45 } 46 47 int main() 48 { 49 // freopen("in.txt", "r", stdin); 50 51 int q, kase = 1, tval, a, b; 52 while(scanf("%d%d%d", &n, &m, &q)!=EOF){ 53 if(!n && !m && !q)break; 54 if(kase!=1)printf("\n"); 55 memset(dis, 0x3f, sizeof dis); 56 memset(Map, 0x3f, sizeof Map); 57 for(int i=1; i<=n; i++){ 58 vex[i].tag = i; 59 scanf("%d", &vex[i].val); 60 } 61 for(int i=0; i<m; i++){ 62 scanf("%d%d%d", &a, &b, &tval); 63 Map[a][b] = min(Map[a][b], tval); 64 Map[b][a] = min(Map[b][a], tval); 65 } 66 sort(vex+1, vex+n+1, cmp); 67 floyd(); 68 printf("Case #%d\n", kase++); 69 for(int i=0; i<q; i++){ 70 scanf("%d%d", &a, &b); 71 int ans = INF, inv = 0; 72 for(int j=1; j<=n; j++)if(vex[j].tag==a || vex[j].tag==b)inv = max(inv, vex[j].val); 73 for(int j=1; j<=n; j++){ 74 ans = min(ans, dis[a][b][j]+max(vex[j].val, inv)); 75 } 76 if(ans!=INF)printf("%d\n", ans); 77 else printf("-1\n"); 78 } 79 } 80 return 0; 81 }