uva 10246(变形floyd)

这道题是world finals的热身赛第一题。弱菜花了两个小时在做出来-。-

题意：给你一张无向图，然后给若干个查询，问你任意两个定点之间的最短路。最短路的定义是这样的：每个定点有权值，每个边也有权值，最短路等于路径上的所有边权值之和+所有定点的权值最大值。

思路：这道题先分析一下测试数据，顶点最多只有80个边最多有1000条所以一定是有重边的，这道题又要用邻接矩阵存所以输入的时候注意一下就好了，然后看查询有6000+个所以还是会有很多重复的，因此我们就可以想到用floyd来做这道题了。那么定点的权值怎么处理呢？我们想到了floyd的dp过程是按定点顺序的，所以我们将顶点按照花费排个序，这样有序的dp就能解出答案了。

代码如下：

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <queue>
#include <stack>
#include <vector>
#define MP(a, b) make_pair(a, b)
#define PB(a) push_back(a)

using namespace std;

typedef long long ll;
typedef pair<int ,int> pii;
typedef pair<unsigned int, unsigned int> puu;
typedef pair<int ,double> pid;
typedef pair<ll, int> pli;

const int INF = 0x3f3f3f3f;
const double eps = 1e-6;
const int LEN = 101;
struct V{int tag, val;};
int Map[LEN][LEN], dis[LEN][LEN][LEN], n, m;
V vex[LEN];
inline bool cmp(V a, V b){return a.val<b.val;}

void floyd()
{
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            dis[i][j][0] = Map[i][j];
            if(i==j)dis[i][j][0] = 0;
        }
    }
    for(int x=1; x<=n; x++){
        int k = vex[x].tag;
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                dis[i][j][x] = min(dis[i][j][x-1], dis[i][k][x-1]+dis[k][j][x-1]);
            }
        }
    }
}

int main()
{
//    freopen("in.txt", "r", stdin);

    int q, kase = 1, tval, a, b;
    while(scanf("%d%d%d", &n, &m, &q)!=EOF){
        if(!n && !m && !q)break;
        if(kase!=1)printf("
");
        memset(dis, 0x3f, sizeof dis);
        memset(Map, 0x3f, sizeof Map);
        for(int i=1; i<=n; i++){
            vex[i].tag = i;
            scanf("%d", &vex[i].val);
        }
        for(int i=0; i<m; i++){
            scanf("%d%d%d", &a, &b, &tval);
            Map[a][b] = min(Map[a][b], tval);
            Map[b][a] = min(Map[b][a], tval);
        }
        sort(vex+1, vex+n+1, cmp);
        floyd();
        printf("Case #%d
", kase++);
        for(int i=0; i<q; i++){
            scanf("%d%d", &a, &b);
            int ans = INF, inv = 0;
            for(int j=1; j<=n; j++)if(vex[j].tag==a || vex[j].tag==b)inv = max(inv, vex[j].val);
            for(int j=1; j<=n; j++){
                ans = min(ans, dis[a][b][j]+max(vex[j].val, inv));
            }
            if(ans!=INF)printf("%d
", ans);
            else printf("-1
");
        }
    }
    return 0;
}