HDU 2807 가장 짧 은 경로 (최 단 로 + 행렬 빠 른 비교)

링크: 
http://acm.hdu.edu.cn/showproblem.php?pid=2807
제목:
The Shortest Path
Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 1421    Accepted Submission(s): 436
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
   
   
   
   

 
제목 의 대의:
만약 에 행렬 A * B = C 가 있다 면 A - B 는 단 방향 경로 가 있 고 거 리 는 1 이다.
행렬 을 주 고 두 행렬 의 직접적인 거 리 를 물 어보 세 요.
분석 과 총 결:
1. 이 문제 의 관건 은 행렬 연산 에 있다.
먼저 건축 도 입 니 다. 분명히 건축 도 는 3 층 for 로 순환 해 야 합 니 다.
처음 제 가 했 을 때 곱 한 단 계 를 3 층 for 순환 에 두 었 는데 그 결과 G + + 로 TLE 를 제출 하고 C + + 로 1500 MS + 를 사 용 했 습 니 다.
그리고 그 단 계 를 2 층 순환 에 곱 할 수 있다 는 것 을 알 게 되 었 고 그 결과 순간 1500 MS 에서 350 MS + 로 떨 어 졌 다.
2. 이상 의 운행 시간 은 모두 소박 한 행렬 비교 방식 을 바탕 으로 한다.
우 리 는 두 행렬 의 복잡 도 를 비교 하 는 것 이 O (n ^ 2) 라 는 것 을 알 고 있 습 니 다. 그러면 O (n) 로 내 려 갈 방법 이 있 습 니까?복잡 도가 한 단계 내 려 갔 는데, 그 속도 의 향상 은 매우 객관 적 이다.
그리고 자 료 를 찾 아 방법 을 배 웠 습 니 다.
이 방법 은 주로 모든 행렬 에 하나의 벡터 (이 벡터 는 < 1, 2, 3, 4,... m >) 를 곱 하여 이 행렬 을 1 차원 의 표지 행렬 로 만 든 다음 에 이 표지 행렬 을 이용 하여 두 행렬 이 똑 같은 지 판단 하 는 것 이다.코드 를 구체 적 으로 보다.
1. 소박 한 행렬 비교, 359 MS

//  359 MS
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

typedef int Type;
const int INF = 0x7fffffff;
const int VN  = 100;

struct Matrix{
    Type mat[VN][VN];
    int n, m;
    Matrix(){n=m=VN; memset(mat, 0, sizeof(mat));}
    Matrix(const Matrix&a){
        set_size(a.n, a.m);
        memcpy(mat, a.mat, sizeof(a.mat));
    }
    Matrix& operator = (const Matrix &a){
        set_size(a.n,a.m);
        memcpy(mat, a.mat, sizeof(a.mat));
        return *this;
    }
    void set_size(int row, int column){n=row; m=column;}
    friend Matrix operator *(const Matrix &a,const Matrix &b){
        Matrix ret;
        ret.set_size(a.n, b.m);
        for(int i=0; i<a.n; ++i){
            for(int k=0; k<a.m; ++k)if(a.mat[i][k]){
                for(int j=0; j<b.m; ++j)if(b.mat[k][j]){
                    ret.mat[i][j] = ret.mat[i][j]+a.mat[i][k]*b.mat[k][j];
                }
            }
        }
        return ret;
    }
    friend bool operator==(const Matrix &a,const Matrix &b){
        if(a.n!=b.n || a.m!=b.m)return false;
        for(int i=0; i<a.n; ++i)
            for(int j=0; j<a.m; ++j)
                if(a.mat[i][j]!=b.mat[i][j])return false;
        return true;
    }
};

Matrix arr[VN];
int n, m;
int d[VN][VN];

void init(){
    for(int i=0; i<n; ++i){
        d[i][i] = INF;
        for(int j=i+1; j<n; ++j)
            d[i][j] = d[j][i] = INF;
    }
}

void Floyd(){
    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 main(){
    while(~scanf("%d%d",&n,&m)&&n+m){
        init();
        for(int i=0; i<n; ++i){
            arr[i].set_size(m,m);
            for(int j=0; j<m; ++j){
                for(int k=0; k<m; ++k)
                    scanf("%d",&arr[i].mat[j][k]);
            }
        }
        for(int i=0; i<n; ++i){
            for(int j=0; j<n; ++j)if(i!=j){
                Matrix ret = arr[i]*arr[j];
                for(int k=0; k<n; ++k)if(k!=j&&k!=i){
                    if(ret==arr[k]){
                        d[i][k] = 1;
                    }
                }
            } 
        }
        Floyd();
        scanf("%d",&m);
        for(int i=0; i<m; ++i){
            int u,v;
            scanf("%d %d",&u,&v);
            --u, --v;
            if(d[u][v]!=INF) printf("%d
",d[u][v]);
            else puts("Sorry");
        }
    }
    return 0;
}

2. 빠 른 행렬 비교, 62MS

// 62 MS
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

typedef int Type;
const int INF = 0x7fffffff;
const int VN  = 100;

struct Matrix{
    Type mat[VN][VN];
    int n, m;
    Matrix(){n=m=VN; memset(mat, 0, sizeof(mat));}
    Matrix(const Matrix&a){
        set_size(a.n, a.m);
        memcpy(mat, a.mat, sizeof(a.mat));
    }
    Matrix& operator = (const Matrix &a){
        set_size(a.n,a.m);
        memcpy(mat, a.mat, sizeof(a.mat));
        return *this;
    }
    void set_size(int row, int column){n=row; m=column;}
    friend Matrix operator *(const Matrix &a,const Matrix &b){
        Matrix ret;
        ret.set_size(a.n, b.m);
        for(int i=0; i<a.n; ++i){
            for(int k=0; k<a.m; ++k)if(a.mat[i][k]){
                for(int j=0; j<b.m; ++j)if(b.mat[k][j]){
                    ret.mat[i][j] = ret.mat[i][j]+a.mat[i][k]*b.mat[k][j];
                }
            }
        }
        return ret;
    }
}arr[VN];

struct Node{
    int map[VN];
    void create(Matrix &a, Node &rec){
        for(int i=0; i<a.n; ++i){
            map[i]=0;
            for(int j=0; j<a.m; ++j)
                map[i]+=a.mat[i][j]*rec.map[j];
        }
    }
}rec[VN];

int n, m;
int d[VN][VN];

void init(){
    for(int i=0; i<n; ++i){
        d[i][i] = INF;
        for(int j=i+1; j<n; ++j)
            d[i][j] = d[j][i] = INF;
    }
}

bool cmp(Node &a,Node &b,int n){
    for(int i=0; i<n; ++i)
        if(a.map[i]!=b.map[i])return false;
    return true;
}
void Floyd(){
    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 main(){
    while(~scanf("%d%d",&n,&m)&&n+m){
        init();
        for(int i=0; i<n; ++i){
            arr[i].set_size(m,m);
            for(int j=0; j<m; ++j){
                rec[i].map[j]=0;
                for(int k=0; k<m; ++k){
                    scanf("%d",&arr[i].mat[j][k]);
                    rec[i].map[j] += arr[i].mat[j][k]*(k+1);
                }
            }
        }
        for(int i=0; i<n; ++i){
            for(int j=0; j<n; ++j)if(i!=j){ 
                Node ret;
                ret.create(arr[i], rec[j]);
                for(int k=0; k<n; ++k)if(k!=j&&k!=i){
                    if(cmp(ret, rec[k], m)){
                        d[i][k] = 1;
                    }
                }
            } 
        }
        Floyd();
        scanf("%d",&m);
        for(int i=0; i<m; ++i){
            int u,v;
            scanf("%d %d",&u,&v);
            --u, --v;
            if(d[u][v]!=INF) printf("%d
",d[u][v]);
            else puts("Sorry");
        }
    }
    return 0;
}

  
   
 ——       ，       。
   
    
  
  
  

     
   
   
             
    
  
  
  
    
  
  
  

     
   
   
           http://blog.csdn.net/shuangde800 ， By   D_Double  (     )