Hdu2807The Shortest Path矩阵

　　矩阵相乘，判断之后建图。 注意 A  B  C三个互不相同的城市

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <string.h>
typedef long long LL;
using namespace std;
const int INF =  0xfffffff;
struct Matrix
{
    int m[200][200];
}a[1111];
int Map[200][200];

Matrix Mul(Matrix a, Matrix b,int n)
{
    Matrix ans;
    for (int i = 0; i < n; i++){
        for (int j = 0; j < n; j++){
            ans.m[i][j] = 0;
            for (int k = 0; k < n; k++){
                ans.m[i][j] += a.m[i][k] * b.m[k][j];
            }
        }
    }
    return ans;
}

int judge(Matrix a, Matrix b, int n)
{
    for(int i =0;i<n;i++)
        for(int j=0;j<n;j++)
        if(a.m[i][j]!=b.m[i][j]) return 0;
    return 1;
}

void floyd(int n)
{
    for (int k = 0; k < n;k++)
    for (int i = 0; i < n; i++){
        for (int j = 0; j < n;j++){
        if(i==j||j==k) continue;
        Map[i][j] = min(Map[i][k] + Map[k][j], Map[i][j]);
        }
    }
}

void show(Matrix a,int n)
{
    for(int i =0;i<n;i++){
        for(int j =0 ;j<n;j++)
            printf("%d ",a.m[i][j]);
        printf("
");
    }
}
int main()
{
    int n, m;
    while (scanf("%d%d",&n,&m), n || m){
        for (int i = 0; i < n; i++){
            for (int j = 0; j < m;j++)
            for (int k = 0; k < m; k++)
                scanf("%d", &a[i].m[j][k]);
        }
        for(int i = 0 ;i<n;i++)
            for(int j=0;j<n;j++)
            Map[i][j]=INF;
        for (int i = 0; i < n;i++)
        for (int j = 0; j < n;j++){
                Matrix ans = Mul(a[i], a[j],m);
        for (int k = 0; k < n; k++){
            if (judge(ans, a[k],m))Map[i][k] = 1;
        }
        }
        floyd(n);
        int k;
        scanf("%d",&k);
        while (k--){
            int b; int c;
            scanf("%d%d", &b, &c);
            b--; c--;
            if (Map[b][c]==INF){
                printf("Sorry
");
            }
            else printf("%d
", Map[b][c]);
        }
    }
    return 0;
}