学步园

http://acm.hdu.edu.cn/showproblem.php?pid=2807

题意 ：　类似于最短路，不过几个city之间的联系是从他们的矩阵信息中所得到的。（矩阵A * 矩阵B = 矩阵C 则说明A 于 C 之间单向连通并且距离为1，PS ： 但是并不是说明B可以连通C，因为矩阵乘法位置互换之后结果不一定相等）

思路 ：矩阵乘法复杂度在O（M^3），而枚举每一组A,B,C复杂度又是O（N^3），一开始傻傻的去试了下，果断TLE。好吧，后来把 A * B的结果保存在新的矩阵里，再去寻找是否存在C，使得复杂度大约降到了O(M ^ 3 * N ^ 2)，1900MS险过~~~~囧。

PS : 写矩阵的时候最好使用结构体，这样效率高。

//CNWSYCF

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>

using namespace std;

typedef long long LL;

const int INF = 100000007;
const double eps = 1e-9;
const int maxn = 100;
#define MIN(a,b) (a > b ? b : a)
#define MAX(a,b) (a > b ? a : b)

struct node
{
      int mat[maxn][maxn];
}q[maxn],temp;
struct gogo
{
      int mat[maxn][maxn];
}New[maxn][maxn];
int N,M,G[maxn][maxn];


bool Pd(int a,int b,int c)
{
      for (int i=1;i<=M;i++)
            for (int j=1;j<=M;j++)
                  if (q[c].mat[i][j] != New[a][b].mat[i][j])return 0;
      return 1;
}

void init()
{
      for (int i=1;i<=N;i++)
            for (int j=1;j<=N;j++)
                  if (i != j)G[i][j] = INF;
                  else G[i][j] = 0;
}

void Floyd()
{
      for (int k=1;k<=N;k++)
            for (int i=1;i<=N;i++)
                  for (int j=1;j<=N;j++)
                        G[i][j] = MIN(G[i][k] + G[k][j] , G[i][j]);
}

void Add(int a,int b)
{
      for (int i=1;i<=M;i++)
            for (int j=1;j<=M;j++)
            {
                  int sum = 0;
                  for (int k=1;k<=M;k++)
                        sum += q[a].mat[i][k] * q[b].mat[k][j];
                  New[a][b].mat[i][j] = sum;
            }
}
int main()
{
      while (scanf("%d%d",&N,&M) && (N || M))
      {
            init();
            for (int c=1;c<=N;c++)
            {
                  for (int i=1;i<=M;i++)
                        for (int j=1;j<=M;j++)
                              scanf("%d",&q[c].mat[i][j]);
            }
            for (int i=1;i<=N;i++)
                  for (int j=1;j<=N;j++)
                        Add(i,j);
            for (int k=1;k<=N;k++)
                  for (int i=1;i<=N;i++)
                        for (int j=1;j<=N;j++)
                              if ((i != j && j!= k && k != i) && Pd(i,j,k))
                              {
                                    G[i][k] = 1;
                                    //G[j][k] = 1;
                              }
            Floyd();
            int Q;
            scanf("%d",&Q);
            while (Q--)
            {
                  int a,b;
                  scanf("%d%d",&a,&b);
                  if (G[a][b] < INF)printf("%d\n",G[a][b]);
                  else printf("Sorry\n");
            }
      }
      return 0;
}