The Shortest Path
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1725 Accepted Submission(s): 554
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
Source
这道题感觉蛮好的,用暴力矩阵乘法求解城市a到b是否有距离可以想到,但是用一维矩阵去优化却是我万万难以想到的
看了网上题解才学会如何用一维矩阵去优化,这个优化主要体现在a*b 与c相比O(m^2)转化为O(m),矩阵相乘a*b的O(n^3)转化为O(n^2)
其实主要是根据若a*b=c,则a*b*temp=c*temp,temp是一维矩阵[1,....m],即1到m行,这样就全部转化为一维矩阵去判断了
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<string> #include<queue> #include<algorithm> #include<map> #include<iomanip> #define INF 99999999 using namespace std; const int MAX=80+10; int n,m,dist[MAX][MAX],s,t; int array[MAX][MAX][MAX],temp[MAX][MAX]; //array记录初始矩阵,temp记录array转化后的一维矩阵 void check(int a,int c){//转化为一维矩阵在此处优化大 for(int i=1;i<=m;++i){ if(temp[0][i] != temp[c][i])return; } dist[a][c]=1; } void MakeRoad(int a,int b){ for(int i=1;i<=m;++i){ temp[0][i]=0; for(int j=1;j<=m;++j){//转化为一维矩阵在此处优化大 temp[0][i]+=array[a][i][j]*temp[b][j];//相当于array[a]*array[b]*[0,1,2,3...m];//[0...m-1]是行矩阵 } } for(int i=1;i<=n;++i){ if(i == a || i == b)continue; check(a,i); } } void floyd(){ for(int k=1;k<=n;++k){ for(int i=1;i<=n;++i){ for(int j=1;j<=n;++j){ if(dist[i][k]+dist[k][j]<dist[i][j]){ dist[i][j]=dist[i][k]+dist[k][j]; } } } } } int main(){ while(cin>>n>>m,n+m){ for(int i=1;i<=n;++i){ for(int j=1;j<=m;++j){ temp[i][j]=0; for(int k=1;k<=m;++k){ scanf("%d",&array[i][j][k]); temp[i][j]+=array[i][j][k]*k;//array*[1,...m],[1...m]是一维行矩阵 } } } for(int i=1;i<=n;++i){ for(int j=i+1;j<=n;++j)dist[i][j]=dist[j][i]=INF; } for(int i=1;i<=n;++i){ for(int j=1;j<=n;++j){ if(i == j)continue; MakeRoad(i,j);//创建道路 } } floyd();//求每个点到其他点的距离 cin>>n; for(int i=0;i<n;++i){ scanf("%d%d",&s,&t); if(dist[s][t] == INF)printf("Sorry "); else printf("%d ",dist[s][t]); } } return 0; }