题目链接：https://acm.hdu.edu.cn/showproblem.php?pid=2807

题意重述

有 N 个城市，每个城市对应一个 M x M 矩阵。
如果存在某个城市矩阵 B，使得 A * B = C，就认为有一条从 A 到 C 的有向边，边权为 1。

多次询问 X -> Y 的最短距离：

  • 能到达输出最短路长度
  • 不能到达输出 Sorry

思路

1. 先把“是否有边”算出来

按定义，边 i -> k 存在当且仅当：存在 j，满足 mat[i] * mat[j] = mat[k]。
并且这里按题库实际评测习惯，需要把 A/B/C 当作三个不同城市（下标两两不同），否则容易 Wrong Answer。

做法：

  1. 枚举有序对 (i, j)，计算乘积矩阵 mat[i] * mat[j]。
  2. 如果这个结果等于某个城市矩阵 mat[k]，就连边 i -> k。

为了快速判断“结果矩阵是否在城市集合里”，先把所有城市矩阵做哈希，映射到城市下标列表。

2. 关键剪枝：乘法过程超过 80 立即停

题目给的所有输入整数都在 [0, 80]，所以任意城市矩阵的每个元素都不超过 80。

而矩阵乘法每项是非负和：

res[r][c] = sum(mat[i][r][t] * mat[j][t][c])

如果某个位置在计算中已经 > 80，那么这个乘积矩阵不可能等于任何城市矩阵，当前 (i, j) 可以直接放弃。

这个剪枝非常有效。

3. 最短路

点数 N <= 80，直接 Floyd：

  • dist[i][i] = 0
  • 有边则 dist[i][k] = 1
  • 最后回答询问

复杂度：

  • 建边：最坏 O(N^2 * M^3)，但有上面的 >80 剪枝
  • Floyd：O(N^3)

在题目范围内可过。

C++17 代码

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include <bits/stdc++.h>
using namespace std;

static const int INF = 1e9;

struct HashPair {
    size_t operator()(const pair<unsigned long long, unsigned long long>& p) const {
        return (size_t)(p.first ^ (p.second + 0x9e3779b97f4a7c15ULL + (p.first << 6) + (p.first >> 2)));
    }
};

pair<unsigned long long, unsigned long long> hashMatrix(const vector<int>& a) {
    unsigned long long h1 = 1469598103934665603ULL;
    unsigned long long h2 = 1099511628211ULL;
    for (int x : a) {
        unsigned long long v = (unsigned long long)(x + 1);
        h1 ^= v;
        h1 *= 1099511628211ULL;

        h2 += v + 0x9e3779b97f4a7c15ULL;
        h2 ^= (h2 << 13);
        h2 ^= (h2 >> 7);
        h2 ^= (h2 << 17);
    }
    return {h1, h2};
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    while (cin >> N >> M) {
        if (N == 0 && M == 0) break;

        vector<vector<int>> mats(N, vector<int>(M * M));
        for (int i = 0; i < N; ++i) {
            for (int r = 0; r < M; ++r) {
                for (int c = 0; c < M; ++c) {
                    cin >> mats[i][r * M + c];
                }
            }
        }

        unordered_map<pair<unsigned long long, unsigned long long>, vector<int>, HashPair> pos;
        pos.reserve(N * 2 + 1);
        for (int i = 0; i < N; ++i) {
            pos[hashMatrix(mats[i])].push_back(i);
        }

        vector<vector<int>> dist(N, vector<int>(N, INF));
        for (int i = 0; i < N; ++i) dist[i][i] = 0;

        vector<int> prod(M * M, 0);

        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < N; ++j) {
                if (j == i) continue; // A 和 B 不能是同一个城市
                bool valid = true;

                for (int r = 0; r < M && valid; ++r) {
                    for (int c = 0; c < M; ++c) {
                        int sum = 0;
                        for (int t = 0; t < M; ++t) {
                            sum += mats[i][r * M + t] * mats[j][t * M + c];
                            if (sum > 80) {
                                valid = false;
                                break;
                            }
                        }
                        if (!valid) break;
                        prod[r * M + c] = sum;
                    }
                }

                if (!valid) continue;

                auto key = hashMatrix(prod);
                auto it = pos.find(key);
                if (it == pos.end()) continue;

                for (int k : it->second) {
                    if (k == i || k == j) continue; // A、B、C 下标两两不同
                    if (mats[k] == prod) {
                        dist[i][k] = 1;
                    }
                }
            }
        }

        for (int k = 0; k < N; ++k) {
            for (int i = 0; i < N; ++i) {
                if (dist[i][k] == INF) continue;
                for (int j = 0; j < N; ++j) {
                    if (dist[k][j] == INF) continue;
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }

        int K;
        cin >> K;
        while (K--) {
            int X, Y;
            cin >> X >> Y;
            --X; --Y;
            if (dist[X][Y] == INF) cout << "Sorry\n";
            else cout << dist[X][Y] << '\n';
        }
    }

    return 0;
}

样例解释

样例 1 中，1 -> 3 可以一步到达，所以输出 1。
样例 2 中，1 -> 3 不可达，所以输出 Sorry。

易错点

  1. 图是有向图，A * B = C 不代表 C 能回到 A。
  2. 可能有内容完全相同的城市矩阵，建边时要处理“同矩阵多个下标”。
  3. 这题评测里通常要按“A/B/C 是三个不同城市”处理，下标要两两不同。
  4. 查询下标是 1-based，代码里要转成 0-based。