「洛谷 P2886」Cow Relays - 矩阵乘法 + 最短路 + DP

发表于 更新于 分类于 ， 阅读次数： Disqus：

题意描述

洛谷链接

给定一张 \(t\) 条边的无向连通图，求从 \(s\) 到 \(e\) 经过 \(n\) 条边的最短路长度。

数据范围：\(1 \le n \le 10^6\)、\(2 \le t \le 100\)、\(1 \le s, t \le 1000\)。

解题思路

看到这个数据范围可得出实际点数不超过 \(200\)。可以想到 Floyd 算法。Floyd 的本质就是 DP。它的第 \(k\) 次更新数据就是计算从该点出发不超过 \(k\) 条边所能到达的最短路。于是我们使用邻接矩阵建图的时候可将自环去掉，Floyd 的第 \(k\) 次更新数据就计算的是从该点出发经过恰好 \(k\) 条边所能到达的最短路。

于是我们可以想到使用矩阵加速 Floyd 的计算。我们可以推出广义矩阵乘法：\(C_{i, j} = \min\limits_{1 \le k \le n}\{A_{i, k} + B_{k, j}\}\)，然后将邻接矩阵存在矩阵中即可。这样就可以使用矩阵快速幂求解。计算从 \(s\) 到 \(e\) 经过 \(n\) 条边的最短路即为 \(C^n_{s, t}\)。

写代码时注意离散化即可。

代码演示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <cstdio>
#include <climits>
#include <algorithm>
#include <map>

const int MAXN = 200;

struct Matrix {
    int a[MAXN + 1][MAXN + 1];

    Matrix() { for (int i = 1; i <= MAXN; i++) for (int j = 1; j <= MAXN; j++) a[i][j] = INT_MAX; }

    int &operator()(int i, int j) { return a[i][j]; }
    const int &operator()(int i, int j) const { return a[i][j]; }
};

Matrix operator*(Matrix a, Matrix b) {
    Matrix res;
    for (int i = 1; i <= MAXN; i++) {
        for (int j = 1; j <= MAXN; j++) {
            for (int k = 1; k <= MAXN; k++) {
                if (a(i, k) != INT_MAX && b(k, j) != INT_MAX) {
                    res(i, j) = std::min(res(i, j), a(i, k) + b(k, j));
                }
            }
        }
    }
    return res;
}

Matrix pow(Matrix a, int n) {
    Matrix res = a;
    n--;
    for (; n; n >>= 1, a = a * a) if (n & 1) res = res * a;
    return res;
}

int main() {
    int n, t, s, e;
    scanf("%d %d %d %d", &n, &t, &s, &e);

    Matrix a;
    std::map<int, int> mp;
    int cnt = 0;
    for (int i = 0; i < t; i++) {
        int w, u, v;
        scanf("%d %d %d", &w, &u, &v);
        if (!mp[u]) mp[u] = ++cnt;
        if (!mp[v]) mp[v] = ++cnt;
        a(mp[u], mp[v]) = std::min(a(mp[u], mp[v]), w);
        a(mp[v], mp[u]) = std::min(a(mp[v], mp[u]), w);
    }

    Matrix ans = pow(a, n);
    printf("%d\n", ans(mp[s], mp[e]));

    return 0;
}