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?

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

```  1 #include<cstdio>
2 #include<cstring>
3 #define inf 0x3f3f3f3f
4 using namespace std;
5
6 const int maxn=82;
7 int arr[maxn][maxn][maxn];
8 int ans[maxn][maxn];
9 int tem[maxn][maxn];
10
11 int n,m,w;
12
13 void init(int a[][maxn])
14 {
15     for(int i=1;i<=n;i++)  //城市初始化
16     {
17       for(int j=1;j<=n;j++)
18       {
19              if(i==j)a[i][j]=0;
20              else a[i][j]=inf;
21       }
22     }
23 }
24
25 void floyd(int a[][maxn])    //运用floyd算法求城市间的最短路径
26 {
27    for(int k=1;k<=n;k++)
28    {
29     for(int i=1;i<=n;i++)
30     {
31      for(int j=1;j<=n;j++)
32      {
33         if(ans[i][j]>ans[i][k]+ans[k][j])
34           ans[i][j]=ans[i][k]+ans[k][j];
35      }
36     }
37    }
38 }
39
40 void Matrix(int a[][maxn],int p1,int p2)
41 {
42     for(int i=1;i<=m;i++)
43     {
44       for(int j=1;j<=m;j++)
45       {
46         a[i][j]=0;  // init()
47        for(int k=1;k<=m;k++)
48        {
49         a[i][j]+=arr[p1][i][k]*arr[p2][k][j];
50        }
51       }
52     }
53 }
54
55 void work()
56 {
57    int t1,t2,t3;
58   for(int i=1;i<=n;i++)
59   {
60       for(int j=1;j<=n;j++)
61     {
62        if(i==j) continue; //a，b 两数组不能相同
63          Matrix(tem,i,j);  //两个矩阵相乘
64       for(t1=1;t1<=n;t1++)
65       {
66            //a，b,c三数组不能相同
67            if(t1!=i&&t1!=j)
68          {
69             for( t2=1;t2<=m;t2++)
70           {
71              for(t3=1;t3<=m;t3++)
72             {
73               //得到的结果相比较
74               if(tem[t2][t3]!=arr[t1][t2][t3])
75                 goto   loop;
76             }
77           }
78            loop:
79                if(t3>m)
80                   ans[i][t1]=1;
81         }
82     }
83   }
84   }
85 }
86
87 int main()
88 {
89    int a,b;
90   while(scanf("%d%d",&n,&m)&&n+m!=0)
91   {
92        for(int i=1;i<=n;i++)
93        for(int j=1;j<=m;j++)
94          for(int k=1;k<=m;k++)
95              scanf("%d",&arr[i][j][k]);
96       init(ans);
97       work();
98      floyd(ans);
99      scanf("%d",&w);
100      while(w--)
101      {
102         scanf("%d%d",&a,&b);
103         if(ans[a][b]==inf)
104             printf("Sorry\n");
105         else
106             printf("%d\n",ans[a][b]);
107      }
108   }
109  return 0;
110 }```

0 条评论

• hdu------1281 棋盘游戏(最小覆盖点)

棋盘游戏 Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java...

• 排序一栏（总结帖）

学了很多的排序，基数排序，堆排序，希尔排序，选择排序，归并排序，快速排序，冒泡排序.....等等，尽管网上好文，如堆山之牛毛，但是还是没有自己写，来...

• hdu ---(4517)小小明系列故事——游戏的烦恼(Dp)

小小明系列故事——游戏的烦恼 Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 65535/327...

• Hebuter Daily Training 201810

有三个人Y,W,D.每个人都很想去一个地方.但是不好请假.所以能去一个 地方就很好了.Y想出来一个方法.每个人掷骰子.点数最多的赢.就可以去 他想去的地方.Y,...

• Codeforces Round #513 C. Maximum Subrectangle(思维)

题目链接：http://codeforces.com/contest/1060/problem/C

• 牛客NOIP提高组(三)题解

考虑算一个位置的概率，若想要\$k\$步把它干掉，那么与他距离为\$1\$到\$k - 1\$的点都必须阻塞

• 09-排序3 Insertion or Heap Sort (25分)

Insertion sort iterates, consuming one input element each repetition, and growin...

• 395. Longest Substring with At Least K Repeating Characters

这是一个经典的分治法解决的问题，关键在于我们如何将这个问题分解为更小的子问题。反过来想，这个子字符串一定不包含什么元素呢？当一个元素出现的总次数小于k，那么该元...

• Wannafly挑战赛27

给出长度为n的序列a, 求有多少对数对 (i, j) (1 <= i < j <= n) 满足 ai + aj 为完全平方数。

• cf1000F. One Occurrence(线段树 set)

首先把询问离线，预处理每个数的\(pre, nxt\)，同时线段树维护\(pre\)(下标是\(pre\)，值是\(i\))，同时维护一下最大值