HDU 2807 The Shortest Path(矩阵相乘+Floyd)

HDU 2807 The Shortest Path(矩阵比较+Floyd)

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

题意:有N个城市,每个城市用一个M*M的矩阵表示.如果矩阵A*矩阵B== 矩阵C,那么我们说城市A到城市C有一条长度为1的路.现在你要回答对于特定的两个城市是否存在路,如果存在的话,最短路是多少?

分析:

本题可以直接暴力枚举任意两个城市a和b然后看他们相乘的结果是否和N个矩阵里面的c矩阵相等.如果相等,那么a->c有长为1的路.注意:这里a与b与c要互不相同. a与b不同是题目要求的,a与c也要不同.因为如果a和c是同一个城市,那么a有一条到自己的长度为1的边,明显不对.

网上也有很多用矩阵乘法优化之后来做比较的.具体思路是:

“如果A*B=C，则A*B*D=C*D，D为m*1的矩阵。设d=B*D，则A*B*D=A*d；同样设dd=A*d，cc=C*D；最后比较dd是否等cc就行了。”

这里我有个疑问,上面的证明只能推出A*B=C -> dd=cc. 但是dd=cc能推出A*B=C吗? 不一定吧? 因为D矩阵是m*1阶的,都不存在逆矩阵.

AC代码: 暴力解决.250ms,与上面的优化相比也没慢多少.不过注意我代码中矩阵相乘的实现方式.

#include<cstdio>
#include<cstring>
#include<algorithm>
#define INF 1e9
using namespace std;
const int maxn=80+5;
int n,m;
struct Matrix
{
    int v[maxn][maxn];
    Matrix(){ memset(v,0,sizeof(v)); }
    void read(int m)
    {
        for(int i=0;i<m;i++)
        for(int j=0;j<m;j++)
            scanf("%d",&v[i][j]);
    }
    Matrix operator*(Matrix &B)const
    {
        Matrix C;
        for(int i=0;i<m;i++)
        for(int k=0;k<m;k++)if(v[i][k])//若按正常的i,j,k顺序循环,则会变成1700ms
        for(int j=0;j<m;j++)if(B.v[k][j])
            C.v[i][j] += v[i][k]*B.v[k][j];
        return C;
    }
    bool operator == (Matrix &B)const
    {
        for(int i=0;i<m;i++)
            for(int j=0;j<m;j++)
                if(v[i][j]!=B.v[i][j]) return false;
        return true;

    }
}ma[maxn];
int d[maxn][maxn];
int main()
{
    while(scanf("%d%d",&n,&m)==2&&n)
    {
        for(int i=0;i<n;i++)
            ma[i].read(m);

        for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            d[i][j]= i==j?0:INF;

        for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)if(i!=j)
        {
            Matrix res = ma[i]*ma[j];
            for(int k=0;k<n;k++)if(i!=k&&j!=k)
                if(res == ma[k])
                    d[i][k]=1;
        }

        for(int k=0;k<n;k++)
        for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
        if(d[i][k]<INF && d[k][j]<INF)
            d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
        int k;
        scanf("%d",&k);
        while(k--)
        {
            int u,v;
            scanf("%d%d",&u,&v);
            u--,v--;
            if(d[u][v]==INF) printf("Sorry\n");
            else printf("%d\n",d[u][v]);
        }
    }
    return 0;
}