The Shortest Path
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2440 Accepted Submission(s): 784
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?
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].
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".
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
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
Sorry
Source
题目很清楚：
如果满足A*B=C 那么就说A到C是联通的....
反之则为不连通...
这里需要用到的求最短路径，对于稠密图的，用弗洛伊德算法比狄斯喹诺算法要好一点。
至于要优化，看来结题报告之后，觉得还是不大靠谱，就没有写，写的是一个朴素的矩阵相乘算法+floyd算法
代码：
#include<cstdio>
#include<cstring>
#define inf 0x3f3f3f3f
using namespace std; const int maxn=;
int arr[maxn][maxn][maxn];
int ans[maxn][maxn];
int tem[maxn][maxn]; int n,m,w; void init(int a[][maxn])
{
for(int i=;i<=n;i++) //城市初始化
{
for(int j=;j<=n;j++)
{
if(i==j)a[i][j]=;
else a[i][j]=inf;
}
}
} void floyd(int a[][maxn]) //运用floyd算法求城市间的最短路径
{
for(int k=;k<=n;k++)
{
for(int i=;i<=n;i++)
{
for(int j=;j<=n;j++)
{
if(ans[i][j]>ans[i][k]+ans[k][j])
ans[i][j]=ans[i][k]+ans[k][j];
}
}
}
} void Matrix(int a[][maxn],int p1,int p2)
{
for(int i=;i<=m;i++)
{
for(int j=;j<=m;j++)
{
a[i][j]=; // init()
for(int k=;k<=m;k++)
{
a[i][j]+=arr[p1][i][k]*arr[p2][k][j];
}
}
}
} void work()
{
int t1,t2,t3;
for(int i=;i<=n;i++)
{
for(int j=;j<=n;j++)
{
if(i==j) continue; //a，b 两数组不能相同
Matrix(tem,i,j); //两个矩阵相乘
for(t1=;t1<=n;t1++)
{
//a，b,c三数组不能相同
if(t1!=i&&t1!=j)
{
for( t2=;t2<=m;t2++)
{
for(t3=;t3<=m;t3++)
{
//得到的结果相比较
if(tem[t2][t3]!=arr[t1][t2][t3])
goto loop;
}
}
loop:
if(t3>m)
ans[i][t1]=;
}
}
}
}
} int main()
{
int a,b;
while(scanf("%d%d",&n,&m)&&n+m!=)
{
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
for(int k=;k<=m;k++)
scanf("%d",&arr[i][j][k]);
init(ans);
work();
floyd(ans);
scanf("%d",&w);
while(w--)
{
scanf("%d%d",&a,&b);
if(ans[a][b]==inf)
printf("Sorry\n");
else
printf("%d\n",ans[a][b]);
}
}
return ;
}