HDU 2807 The Shortest Path（最短路+矩阵快速比较）
链接:
http://acm.hdu.edu.cn/showproblem.php?pid=2807
题目：
The Shortest PathTime Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1421 Accepted Submission(s): 436
Problem DescriptionThere 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?
InputEach 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].
OutputFor 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 Input3 21 12 21 11 12 24 411 33 21 12 21 11 12 24 311 30 0
Sample Output1Sorry
题目大意：
如果矩阵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
// 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;}—— 生命的意义，在于赋予它意义。
原创 http://blog.csdn.net/shuangde800 ， By D_Double (转载请标明)