HDU 2807 The Shortest Path：最短路+矩阵快速比较

HDU 2807 The Shortest Path：最短路+矩阵快速比较2014-12-04 csdn博客 shuangde800链接:

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 21 12 21 11 12 24 411 33 21 12 21 11 12 24 311 30 0

Sample Output

1Sorry

题目大意：

如果矩阵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
",d[u][v]）;else puts（"Sorry"）;}}return 0;}

2. 快速矩阵比较， 62MS

更多精彩内容：http://www.bianceng.cn/Programming/sjjg/