HDU 2807 The Shortest Path（最短路+矩阵高速比较）
HDU 2807 The Shortest Path（最短路+矩阵快速比较）
Total Submission(s): 1421 Accepted Submission(s): 436
链接:
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?
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循环。
第一次我做的时是把相乘的那一步放在第三层for循环里，结果导致用G++提交TLE， 用C++提交用了1500MS+.
然后发现其实可以把相乘那一步放在第二层循环里的，结果瞬间从1500MS 降到了350MS+
2. 以上的运行时间都是基于朴素的矩阵比较方式。
我们知道要比较两个矩阵的复杂度是O(n^2)， 那么有没有办法降到O(n)呢？ 复杂度降了一阶，那速度的提升是很客观的。
然后查了下资料，学习了一种方法。
这个方法主要是让每个矩阵乘上一个向量(这个向量是<1,2,3,4,...m>)，让这个矩阵变成一个一维的标识矩阵，之后就利用这个标识矩阵来判断两个矩阵是否相等。具体看代码。
1.朴素的矩阵比较， 359MS
// 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\n",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\n",d[u][v]);
else puts("Sorry");
}
}
return 0;
}
—— 生命的意义，在于赋予它意义。