The Shortest Path

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1827 Accepted Submission(s): 589

Problem Description

There are N cities in the country. Each city is represent by a matrix size of M*M. If city A, B and C satisfy that A*B = C, we say that there is a road from A to C with distance 1 (but that does not means there is a road from C to A).
Now the king of the country wants to ask me some problems, in the format:
Is there is a road from city X to Y?
I have to answer the questions quickly, can you help me?

Input

Each test case contains a single integer N, M, indicating the number of cities in the country and the size of each city. The next following N blocks each block stands for a matrix size of M*M. Then a integer K means the number of questions the king will ask, the following K lines each contains two integers X, Y(1-based).The input is terminated by a set starting with N = M = 0. All integers are in the range [0, 80].

Output

For each test case, you should output one line for each question the king asked, if there is a road from city X to Y? Output the shortest distance from X to Y. If not, output "Sorry".

Sample Input

3 2

1 1

2 2

1 1

1 1

2 2

4 4

1

1 3

3 2

1 1

2 2

1 1

1 1

2 2

4 3

1

1 3

0 0

Sample Output

1

Sorry

　　题意：给你n个m*m的矩阵，如果某个矩阵A*不是A的某个矩阵B=非A、B的矩阵C(这里的ABC只是编号上面的不一样)，那么就说明A到C有一条有向边，长度为1，然后给你q个询问，求询问中Ｘ到Ｙ的最短路，如果Ｘ到Ｙ没有路，就输出Sorry。

　　这一题的实质就是一个矩阵的乘法、矩阵的相等判定以及最短路，矩阵的乘法直接按照定义求，对于判定相等，可以直接逐个位置的元素判定是否相等也可以用memcmp()函数来判断，不过如果是用后者的话要注意空余的位置要在一开始赋值为0或者-1，总之就是排除干扰的因素，最短路这里用了Flyod。

　　这一题难度其实不是很大，就是做的时候有点累，结果敲完代码以后交上去一直WA，后来检查代码才发现Flyod写好了但是没有调用= =。

　　看来要注意合理休息。

代码：

#include <cstdio>
#include <cstring>
#define INF 1000000000
#define MAX 80
using namespace std;

int n,m,dis[MAX][MAX];

typedef struct Mat
{
   int city[MAX][MAX];

   void Init()
   {
       memset(city,0,sizeof(city));
   }

   void Insert()
   {
       int i,j;
       Init();
       for(i=0;i<m;i++)
       {
           for(j=0;j<m;j++)
           {
               scanf("%d",&city[i][j]);
           }
       }
   }

   void print()
   {
       int i,j;
       for(i=0;i<m;i++)
       {
           for(j=0;j<m;j++)
           {
               printf("%d ",city[i][j]);
           }
           printf("
");
       }
   }

   Mat operator * (const Mat &b)
   {
       int i,j,u;
       Mat c;
       c.Init();
       for(u=0;u<m;u++)
       {
           for(i=0;i<m;i++)
           {
               if(!city[i][u]) continue;
               for(j=0;j<m;j++)
               {
                   c.city[i][j]+=city[i][u]*b.city[u][j];
               }
           }
       }
       return c;
   }

   bool operator == (const Mat &b)
   {
       return (memcmp(city,b.city,sizeof(city))==0);
       /*
       int i,j;
       for(i=0;i<m;i++)
       {
           for(j=0;j<m;j++)
           {
               if(city[i][j]!=b.city[i][j]) return 0;
           }
       }
       return 1;
       */
   }
}Mat;

Mat mat[1000];

void Flyod()
{
   int i,j,u;
   for(u=1;u<=n;u++)
   {
       for(i=1;i<=n;i++)
       {
           for(j=1;j<=n;j++)
           {
               int len=dis[i][u]+dis[u][j];
               if(dis[i][j]>len) dis[i][j]=len;
           }
       }
   }

}

int main()
{
   int i,j,u,q,a,b;
   //freopen("data.txt","r",stdin);
   while(scanf("%d %d",&n,&m),(n+m))
   {
       for(i=1;i<=n;i++)
       {
           mat[i].Insert();
           //mat[i].print();
       }
       for(i=1;i<=n;i++)
       {
           for(j=1;j<=n;j++)
           {
               dis[i][j]= i==j ? 0 : INF;
           }
       }
       for(i=1;i<=n;i++)
       {
           for(j=1;j<=n;j++)
           {
               if(i==j) continue;
               Mat c=mat[i]*mat[j];
               for(u=1;u<=n;u++)
               {
                   if(i==u || j==u) continue;
                   if(c==mat[u]) dis[i][u]=1;
               }
           }
       }
       Flyod();
       scanf("%d",&q);
       for(i=0;i<q;i++)
       {
           scanf("%d %d",&a,&b);
           if(dis[a][b]<INF) printf("%d
",dis[a][b]);
           else printf("Sorry
");
       }
   }
   return 0;
}
2807