最短路。全源最短路，使用floyd。
给你很多个矩阵，每个矩阵代表一个点，两点之间有一条有向边（A->C，权值为1）当且仅当A*B=C（矩阵运算），其中A,B,C代表不同的点。然后给很多个查询，每次问你从一个点到另一个点的最短路。
主要注意上述A,B,C指代不同的点。
话说刚刚看了一下别的题解，居然发现还有 快速矩阵比较 这种东西，能O(n)完成矩阵比较？。。太秀了
#include#include #include #include #include #include using namespace std;const int INF = 1e9;const int MAX = 81;int N, M, Q;int mtx[MAX][MAX][MAX];int d[MAX][MAX]; // 邻接矩阵int t[MAX][MAX]; // 存储矩阵乘积的临时矩阵void init(){ for (int i = 1; i <= N; i++) { for (int j = 1; j <= N; j++) { if (i != j) d[i][j] = INF; else d[i][j] = 0; // 使用邻接矩阵时这一步还是必要的，至少稳当 } }}void mul(int a, int b) // a*b=c{ int s; for (int i = 1; i <= M; i++) { for (int j = 1; j <= M; j++) { s = 0; for (int k = 1; k <= M; k++) { s += mtx[a][i][k] * mtx[b][k][j]; } t[i][j] = s; } }}void floyd(){ for (int k = 1; k <= N; k++) for (int i = 1; i <= N; i++) for (int j = 1; j <= N; j++) { if(d[i][k] != INF && d[k][j] != INF && d[i][k] + d[k][j] < d[i][j]) { d[i][j] = d[i][k] + d[k][j]; } }}bool equal(int x){ for (int i = 1; i <= M; i++) { for (int j = 1; j <= M; j++) { if (mtx[x][i][j] != t[i][j]) return false; } } return true;}int main(){ int a, b; for (; ~scanf("%d%d", &N, &M);) { if (!N && !M) break; init(); for (int i = 1; i <= N; i++) for (int j = 1; j <= M; j++) for (int k = 1; k <= M; k++) scanf("%d", &mtx[i][j][k]); for (int i = 1; i <= N; i++) { for (int j = 1; j <= N; j++) { if (i == j) continue; // 人家题目中说了A,B,C是三个城市，不能指代相同 mul(i, j); // 把矩阵乘法放在第二层进行，不要放到第三层 for (int k = 1; k <= N; k++) { if (k == i || d[i][k] == 1) continue; if (k == j) continue; // 没加这个就 WA，看来里面有单位矩阵（A） // 按照题目规矩来，人家说了A,B,C是三个城市，这就意味着不能指代相同 if (equal(k)) d[i][k] = 1; } } } floyd(); scanf("%d", &Q); for (; Q--;) { scanf("%d%d", &a, &b); if (d[a][b] == INF) printf("Sorry\n"); else printf("%d\n", d[a][b]); } } return 0;}