链接:
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循环。
第一次我做的时是把相乘的那一步放在第三层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
更多精彩内容：http://www.bianceng.cn/Programming/sjjg/
以上是小编为您精心准备的的内容，在的博客、问答、公众号、人物、课程等栏目也有的相关内容，欢迎继续使用右上角搜索按钮进行搜索int
， 矩阵
， matrix
， java 矩阵
， const
， mat
， 矩阵运算
， single ask
The
hdu快速幂、矩阵快速幂、矩阵快速幂模板、稀疏矩阵快速转置算法、快速矩阵乘法，以便于您获取更多的相关知识。