hdu 2807(矩阵+floyed)

The Shortest Path

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

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

Sample Output

1
Sorry

暴力竟然过了,O(N^5)这题数据多水。。。要注意A,B,C矩阵不能够相同（A,B和A,C一般能够注意,主要是B,C不能相同）

#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <math.h>
#include <queue>
using namespace std;
const int N = 100;
const int INF= 99999999;
struct Matrix
{
    int v[N][N];
} M[N];
int n,m;
int graph[N][N];
Matrix mult(Matrix a,Matrix b)
{
    Matrix temp;
    memset(temp.v,0,sizeof(temp.v));
    for(int i=0; i<m; i++)
    {
        for(int j=0; j<m; j++)
        {
            for(int k=0; k<m; k++)
            {
                temp.v[i][j] += a.v[i][k]*b.v[k][j];
            }
        }
    }
    return temp;
}
bool Judge(Matrix a,Matrix b)
{
    for(int i=0; i<m; i++)
    {
        for(int j=0; j<m; j++)
        {
            if(a.v[i][j]!=b.v[i][j]) return false;
        }
    }
    return true;
}
int main()
{
    while(scanf("%d%d",&n,&m)!=EOF,n+m)
    {
        for(int i=0; i<n; i++)
        {
            for(int j=0; j<n; j++)
            {
                if(i==j) graph[i][j] = 0;
                else graph[i][j]=INF;
            }
        }
        for(int i=0; i<n; i++)
        {
            for(int j=0; j<m; j++)
            {
                for(int k=0; k<m; k++)
                {
                    scanf("%d",&M[i].v[j][k]);
                }
            }
        }
        for(int i=0; i<n; i++)
        {
            for(int j=0; j<n; j++)
            {
                if(i!=j)
                {
                    Matrix t = mult(M[i],M[j]);
                    for(int k=0; k<n; k++)
                    {
                        if(i!=k&&j!=k&&Judge(t,M[k]))  ///这里要注意:矩阵i,j,k不能够相同
                        {
                            graph[i][k]=1;
                        }
                    }
                }
            }
        }
        for(int k=0; k<n; k++)
        {
            for(int i=0; i<n; i++)
            {
                for(int j=0; j<n; j++)
                {
                    graph[i][j] = min(graph[i][j],graph[i][k]+graph[k][j]);
                }
            }
        }
        int t ;
        scanf("%d",&t);
        while(t--)
        {
            int a,b;
            scanf("%d%d",&a,&b);
            a--,b--;
            if(graph[a][b]>=INF) printf("Sorry
");
            else printf("%d
",graph[a][b]);
        }
    }
}