题解 P2966 【[USACO09DEC]Cow Toll Paths G】

· · 题解

Description

P2966
给定一张图，求 q 组询问，s_i 到 t_i 的边权之和与点权的最大值的和的最小值。

Solution

Floyd。

首先是对点权进行排序（记得要记原来的顺序，以便之后跑 floyd）。

然后邻接表存边，floyd 的经典操作。

然后就三重循环跑 floyd 即可，注意 dist 是跑边权，ans 是边权与点权。

我们用上 floyd 的转移公式：

dist_{i,j}=\min\{dist_{i,j},dist_{i,k}+dist_{k,j}\}

注意，这时候不能直接用 i,j,k，因为点权是排过序的，所以都要转变成 c_i.dis，c_j.dis，c_k.dis。

最后 ans 的转移公式就很简单了，按照题目所说的：

ans_{i,j}=\min\{ans_{i,j},dist_{i,j}+\max\{c_i.val,c_j.val,c_k.val\}\}

跟上面 dist 的转移公式一样，i,j,k 还是要转变为 c_i.dis，c_j.dis，c_k.dis。

最后输出 ans_{a,b} 即可。

注意：上面的 dis 和 val 代表的具体内容可以看下方的代码。

Code 1

#include <bits/stdc++.h>

using namespace std;

int n, m, q;
int ans[1005][1005], dist[1005][1005]; 
const int inf = 0x3f3f3f3f;

struct node {
    int val, dis;
} c[1005];

bool cmp (node x, node y) {
    return x.val < y.val;
}

int main () {
    scanf("%d%d%d", &n, &m, &q);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &c[i].val);
        c[i].dis = i;
    }
    sort(c + 1, c + n + 1, cmp);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) 
            if (i == j) dist[i][j] = 0;
            else dist[i][j] = inf;
    memset(ans, 0x3f, sizeof(ans));
    for (int i = 1, u, v, w; i <= m; i++) {
        scanf("%d%d%d", &u, &v, &w);
        dist[u][v] = w;
        dist[v][u] = w;
    }
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++) {
                dist[c[i].dis][c[j].dis] = min(dist[c[i].dis][c[j].dis], dist[c[i].dis][c[k].dis] + dist[c[k].dis][c[j].dis]);
                ans[c[i].dis][c[j].dis] = min(ans[c[i].dis][c[j].dis], dist[c[i].dis][c[j].dis] + max(c[i].val, max(c[j].val, c[k].val)));
            }
    while (q--) {
        int a, b;
        scanf("%d%d", &a, &b);
        printf("%d\n", ans[a][b]);
    }
    return 0;
}

预测得分：50 分
为什么只有 50 分呢 …… 因为题目中说了可能要有重边
所以我们要处理一下重边

Code 2

#include <bits/stdc++.h>

using namespace std;

int n, m, q;
int ans[1005][1005], dist[1005][1005]; 
const int inf = 0x3f3f3f3f;

struct node {
    int val, dis;
} c[1005];

bool cmp (node x, node y) {
    return x.val < y.val;
}

int main () {
    scanf("%d%d%d", &n, &m, &q);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &c[i].val);
        c[i].dis = i;
    }
    sort(c + 1, c + n + 1, cmp);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) 
            if (i == j) dist[i][j] = 0;
            else dist[i][j] = inf;
    memset(ans, 0x3f, sizeof(ans));
    for (int i = 1, u, v, w; i <= m; i++) {
        scanf("%d%d%d", &u, &v, &w);
        dist[u][v] = min(dist[u][v], w);
        dist[v][u] = min(dist[v][u], w);
    }
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++) {
                dist[c[i].dis][c[j].dis] = min(dist[c[i].dis][c[j].dis], dist[c[i].dis][c[k].dis] + dist[c[k].dis][c[j].dis]);
                ans[c[i].dis][c[j].dis] = min(ans[c[i].dis][c[j].dis], dist[c[i].dis][c[j].dis] + max(c[i].val, max(c[j].val, c[k].val)));
            }
    while (q--) {
        int a, b;
        scanf("%d%d", &a, &b);
        printf("%d\n", ans[a][b]);
    }
    return 0;
}

预测得分：100 分
AC Link!

By Shuchong
2020.7.17