注意题目的一个重要细节...A*B=C..并且A,B,C分别是三个不同的城市
矩阵相乘构造图时..注意..枚举了当前A,B后..先算出矩阵.再来找C....
最后Floyd跑出答案...
我写的很暴力了...对于矩阵比较这一块..看别人的题解...有更好的方法...用把每个矩阵*向量(1,2,3,4...m)变成一个1维的向量..再进行比较...
Program:
#include<iostream> #include<stdio.h> #include<string.h> #include<cmath> #include<queue> #include<stack> #include<set> #include<algorithm> #define ll long long #define oo 1000000007 #define pi acos(-1.0) #define MAXN 85 using namespace std; struct node { int s[MAXN][MAXN]; }City[MAXN]; int N,M; int arc[MAXN][MAXN]; node mul(node a,node b) { int i,j,k; node h; memset(h.s,0,sizeof(h.s)); for (k=1;k<=M;k++) for (i=1;i<=M;i++) for (j=1;j<=M;j++) h.s[i][j]+=a.s[i][k]*b.s[k][j]; return h; } void Floyd() { int k,i,j; for (k=1;k<=N;k++) for (i=1;i<=N;i++) for (j=1;j<=N;j++) arc[i][j]=min(arc[i][j],arc[i][k]+arc[k][j]); return; } int main() { int i,t,j,x,k; node p; while (~scanf("%d%d",&N,&M) && N && M) { for (t=1;t<=N;t++) for (i=1;i<=M;i++) for (j=1;j<=M;j++) scanf("%d",&City[t].s[i][j]); memset(arc,0x3f,sizeof(arc)); for (i=1;i<=N;i++) arc[i][i]=0; for (t=1;t<=N;t++) for (i=1;i<=N;i++) if (i!=t) { p=mul(City[i],City[t]); for (j=1;j<=N;j++) { if (j==t || j==i) continue; for (x=1;x<=M;x++) for (k=1;k<=M;k++) if (p.s[x][k]!=City[j].s[x][k]) goto A; arc[i][j]=1; A: ; } } Floyd(); scanf("%d",&t); while (t--) { scanf("%d%d",&i,&j); if (arc[i][j]>oo) printf("Sorry\n"); else printf("%d\n",arc[i][j]); } } return 0; }