题意：
有N个顶点，每个顶点由M*M矩阵构成， 对于顶点 A, B，C， 若 A*B = C，则存在一条路 (a,c)路径为1，
K次询问，问 (x,y)最短路径。 N,M 《= 100
解法：
用矩阵乘法 暴力找出 顶点间关系， 然后Floyd跑一次。
好久没写矩阵乘法了。顺便当模板敲一次。
View Code #include#include #include #include using namespace std;const int inf = 0x3f3f3f3f;const int N = 101;int n, m; struct Matrix{ int mat[N][N]; Matrix(){ memset(mat,0,sizeof(mat)); } void input(){ for(int i = 0; i < m; i++) for(int j = 0; j < m; j++) scanf("%d",&mat[i][j] ); } void unit(){ memset(mat,0,sizeof(mat)); for(int i = 0; i < m; i++) mat[i][i] = 1; } Matrix& operator = (const Matrix &a){ memcpy( mat, a.mat, sizeof(a.mat)); return *this; } friend Matrix operator * (const Matrix &a, const Matrix &b){ Matrix res; for(int i = 0; i < m; i++) for(int k = 0; k < m; k++) if( a.mat[i][k] ) for(int j = 0; j < m; j++) res.mat[i][j] += a.mat[i][k]*b.mat[k][j]; return res; } friend bool operator == (const Matrix &a, const Matrix &b){ for(int i = 0; i < m; i++) for(int j = 0; j < m; j++) if( a.mat[i][j] != b.mat[i][j] ) return false; return true; } };int dis[N][N];Matrix A[N];void floyd(){ for(int k = 0; k < n; k++) for(int i = 0; i < n; i++) if( dis[i][k] != inf ) for(int j = 0; j < n; j++) if( dis[i][j] > dis[i][k] + dis[k][j] ) dis[i][j] = dis[i][k] + dis[k][j]; }int main(){ while( scanf("%d%d", &n,&m), n+m ){ for(int i = 0; i < n; i++) A[i].input(); memset(dis, 0x3f, sizeof(dis)); for(int i = 0; i < n; i++) for(int j = 0; j < n; j++){ Matrix t = A[i]*A[j]; for(int k = 0; k < n; k++) if( t == A[k] && (k!=i && k!=j) )//不明觉厉... dis[i][k] = 1; } floyd(); int a, b, k;scanf("%d", &k); for(int i = 0; i < k; i++){ scanf("%d%d",&a,&b); if( dis[a-1][b-1] == inf ) printf("Sorry\n"); else printf("%d\n", dis[a-1][b-1] ); } } return 0;}