难度一般,坑了我好久,并且现学了一下矩阵乘法
题目连接:http://acm.hdu.edu.cn/showproblem.php?pid=2807
AC代码
#include<bits/stdc++.h> using namespace std; #define INT_MAX 0x73f3f3f typedef struct W_w{ int sum[100][100]; }wang; wang y[100]; int m,n; int mp[100][100]; wang z; bool bj(wang a,wang b){ for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ if(a.sum[i][j]!=b.sum[i][j]) return false; } } return true; } void jzc(int a,int b){ for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ int sum=0; for(int k=0;k<n;k++){ sum+=y[a].sum[i][k]*y[b].sum[k][j]; } z.sum[i][j]=sum; } } // for(int i=0;i<n;i++){ // for(int j=0;j<n;j++){ // printf("%d ",y[a].sum[i][j]); // } // printf(" "); // } // printf(" "); // for(int i=0;i<n;i++){ // for(int j=0;j<n;j++){ // printf("%d ",y[b].sum[i][j]); // } // printf(" "); // } // printf(" "); // for(int i=0;i<n;i++){ // for(int j=0;j<n;j++){ // printf("%d ",z.sum[i][j]); // } // printf(" "); // } // printf(" "); } void floyd(){ for(int k=0;k<m;k++){ for(int i=0;i<m;i++){ //if(i==j) continue; for(int j=0;j<m;j++){ if(mp[i][k]+mp[k][j]<mp[i][j]){ mp[i][j]=mp[i][k]+mp[k][j]; } } } } } int main() { while(~scanf("%d %d",&m,&n)){ if(m==0&&n==0) break; for(int i=0;i<99;i++){ for(int j=0;j<99;j++){ if(i==j){ mp[i][j]=0; } else{ mp[i][j]=100000000; } } } memset(y,0,sizeof(y)); for(int i=0;i<m;i++){ for(int j=0;j<n;j++){ for(int k=0;k<n;k++){ scanf("%d",&y[i].sum[j][k]); } } } for(int i=0;i<m;i++){ for(int j=0;j<m;j++){ if(i==j) continue; jzc(i,j); // for(int a=0;a<n;a++){ // for(int b=0;b<n;b++){ // printf("+%d ",z.sum[a][b]); // } // printf(" "); // } for(int k=0;k<m;k++){ if(k==j||k==i) continue; if(bj(z,y[k])){ mp[i][k]=1; mp[j][k]=1; } } } } floyd(); int kk; scanf("%d",&kk); for(int i=0;i<kk;i++){ int a,b; scanf("%d %d",&a,&b); if(mp[a-1][b-1]==100000000){ printf("Sorry "); } else printf("%d ",mp[a-1][b-1]); } } return 0; } /* 3 3 1 1 2 2 2 3 3 3 5 1 1 6 1 1 2 2 2 1 4 4 4 3 3 3 2 2 2 1 1 3 */