findthepath.cpp

第四届百度杯编程大赛final解题报告+标程

/*
 * Author: [e-mail]
 * Created Time:  2/17/2009 2:37:09 PM
 * File Name: FindThePath.cpp
 * Description: 
 What you need to know before you read this code is the real process of floyd.
 Why we call it as a DP algorithm?
 If you understand that algorithm, I think you could solved this problem quackly.
 */
#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
#include <cstdlib>
#include <algorithm>
using namespace std;
#define out(x) fprintf(stderr, "%s: %lld\n", #x, (long long)(x))
#define SZ(v) ((int)(v).size())
const int maxint=-1u>>1;
template <class T> bool get_max(T& a, const T &b) {return b > a? a = b, 1: 0;}
template <class T> bool get_min(T& a, const T &b) {return b < a? a = b, 1: 0;}
int point[210];
int adj[210][210];
int dp[210][210][210];
bool cmp(int a, int b) {
    return point[a] < point[b];
}
int main() {
    int ca;
    scanf("%d", &ca);
    while (ca--) {
        int n, m;
        scanf("%d %d", &n, &m);
        for (int i = 0; i < n; ++i) {
            scanf("%d", point + i);
        }
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                adj[i][j] = maxint;
            }
        }
        int tmp[200];
        for (int i = 0; i < n; ++i) {
            tmp[i] = i;
        }
        sort(tmp, tmp + n, cmp);
        while (m--) {
            int u, v, c;
            scanf("%d %d %d", &u, &v, &c);
            adj[u][v] = adj[v][u] = c;
        }
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                dp[0][i][j] = adj[i][j];
            }
        }
        for (int k = 0; k < n; ++k) {
            int v = tmp[k];
            for (int i = 0; i < n; ++i) {
                for (int j = 0; j < n; ++j) {
                    dp[k + 1][i][j] = dp[k][i][j];
                }
            }
            for (int i = 0; i < n; ++i) {
                if (dp[k][i][v] < maxint) {
                    for (int j = 0; j < n; ++j) {
                        if (dp[k][v][j] < maxint) {
                            get_min(dp[k + 1][i][j], dp[k][i][v] + dp[k][v][j]);
                        }
                    }
                }
            }
        }
        int Q;
        scanf("%d", &Q);
        sort(point, point + n);
        while (Q--) {
            int u, v, k;
            scanf("%d %d %d", &u, &v, &k);
            int ans = adj[u][v];
            int tmp = upper_bound(point, point + n, k) - point;
            get_min(ans, dp[tmp][u][v]);
            if (ans == maxint) {
                printf("-1\n");
            } else {
                printf("%d\n", ans);
            }
        }
        puts("");
    }
    return 0;
}