专栏首页mlhdu-----(2807)The Shortest Path(矩阵+Floyd)

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): 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

HDU 2009-4 Programming Contest

题目很清楚: 

如果满足A*B=C 那么就说A到C是联通的....

反之则为不连通...

这里需要用到的求最短路径,对于稠密图的,用弗洛伊德算法比狄斯喹诺算法要好一点。

至于要优化,看来结题报告之后,觉得还是不大靠谱,就没有写,写的是一个朴素的矩阵相乘算法+floyd算法

代码:

  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...

    Gxjun
  • 排序一栏(总结帖)

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

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

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

    Gxjun
  • Hebuter Daily Training 201810

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

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

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

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

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

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

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

    AI那点小事
  • 395. Longest Substring with At Least K Repeating Characters

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

    眯眯眼的猫头鹰
  • Wannafly挑战赛27

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

    xiaohejun
  • cf1000F. One Occurrence(线段树 set)

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

    attack

扫码关注云+社区

领取腾讯云代金券