hdu 2807 The Shortest Path（矩阵+floyd）

The Shortest Path

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3164 Accepted Submission(s): 1030

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

2 2

4 4

1 3

3 2

1 1

2 2

1 1

2 2

4 3

1 3

0 0

Sample Output

1 Sorry

Source

HDU 2009-4 Programming Contest

题意：先输入n，m，接着输入n个m*m的矩阵，再输入k表示k次询问，接下来输入k行输入x，y，询问x点是否能到y点，可以则输出最短路。当矩阵 A*B = C 的时候，A点到C点的距离是1.

先处理矩阵，建图，此题数据只有85,直接用floyd就好。

附上代码：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 #define N 85
 6 #define INF 0x3f3f3f3f
 7 using namespace std;
 8 int n,m;
 9 int map[N][N];
10 int a[N][N][N],tem[N][N];
11 
12 void floyd()
13 {
14     int i,j,k;
15     for(k=1; k<=n; k++)
16         for(i=1; i<=n; i++)
17             for(j=1; j<=n; j++)
18                 if(map[i][j]>map[i][k]+map[k][j])
19                     map[i][j]=map[i][k]+map[k][j];
20 }
21 
22 void getmap()
23 {
24     int i,j,k,x,y,z;
25     for(i=1; i<=n; i++)
26         for(j=1; j<=m; j++)
27             for(k=1; k<=m; k++)
28                 scanf("%d",&a[i][j][k]);
29     for(i=0; i<=n; i++)
30         for(j=0; j<=n; j++)
31             if(i==j) map[i][j]=0;
32             else   map[i][j]=INF;
33     for(i=1; i<=n; i++)
34     {
35         for(j=1; j<=n; j++)
36         {
37             if(i==j) continue;
38             memset(tem,0,sizeof(tem));
39             for(x=1; x<=m; x++)
40                 for(y=1; y<=m; y++)
41                 {
42                     tem[x][y]=0;
43                     for(z=1; z<=m; z++)   ///矩阵计算
44                         tem[x][y]+=a[i][x][z]*a[j][z][y];
45                 }
46             for(x=1; x<=n; x++)
47             {
48                 if(x==i||x==j)
49                     continue;
50                 int flag=1;
51                 for(y=1; y<=m; y++)
52                 {
53                     for(z=1; z<=m; z++)
54                     {
55                         if(tem[y][z]!=a[x][y][z]) ///比较是否完全相同
56                         {
57                             flag=0;
58                             break;
59                         }
60                     }
61                     if(!flag)
62                         break;
63                 }
64                 if(flag)
65                     map[i][x]=1;
66             }
67         }
68     }
69     floyd();
70 }
71 int main()
72 {
73     int i,j,k,x,y;
74     while(~scanf("%d%d",&n,&m))
75     {
76         if(n==0&&m==0)
77             break;
78         getmap();
79         scanf("%d",&k);
80         while(k--)
81         {
82             scanf("%d%d",&x,&y);
83             if(map[x][y]<INF)
84                 printf("%d
",map[x][y]);
85             else
86                 printf("Sorry
");
87         }
88     }
89     return 0;
90 }