hdu 2807 The Shortest Path

点击打开链接hdu 2807

思路：最短路+floyd+矩阵乘法

分析：
1 题目明确要求x->y是否有了，而且有多次询问，所以序则floyd
2 题目给的点的形式是矩阵，所以还要去处理矩阵，判断A*B=C
3 题目说了A B C三个城市，所以做A B C三个是不同的

代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
#define MAXN 110
#define INF 0xFFFFFFF

int n , m , k;
long long dis[MAXN][MAXN];
int tmp_matrix[MAXN][MAXN];
struct City{
   int matrix[MAXN][MAXN];
}c[MAXN];

/*初始化*/
void init(){
   for(int i = 1 ; i <= n ; i++){
      for(int j = 1 ; j <= n ; j++)
         dis[i][j] = INF;
      dis[i][i] = 0;
   }
}

/*判断是否满足A*B = C*/
bool judge(int i){
   for(int j = 1 ; j <= m ; j++){
      for(int k = 1 ; k <= m ; k++){
        if(c[i].matrix[j][k] != tmp_matrix[j][k])
          return false;
      }
   }
   return true;
}

void solve(){
    for(int i = 1 ; i <= n ; i++){
       for(int j = 1 ; j <= n ; j++){/*枚举矩阵*/
          /*求新矩阵*/
          for(int k = 1 ; k <= m ; k++){
             for(int t = 1 ; t <= m ; t++){
                tmp_matrix[k][t] = 0;
                for(int h = 1 ; h <= m ; h++)
                   tmp_matrix[k][t] += c[i].matrix[k][h]*c[j].matrix[h][t];
             }
          }
          for(int g = 1 ; g <= n ; g++){
             if(judge(g) && g != i && g!= j)
               dis[i][g] = 1;
          }
       }
    }
}

long long min(long long a , long long b){
    return a < b ? a : b;
}

void floyd(){
    for(int k = 1 ; k <= n ; k++){
       for(int i = 1 ; i <= n ; i++){
          for(int j = 1 ; j <= n ; j++)
             dis[i][j] = min(dis[i][k]+dis[k][j] , dis[i][j]);
       }
    }
}

int main(){
   int star , end;
   while(scanf("%d%d", &n , &m) && n+m){
      init();
      for(int i = 1 ; i <= n ; i++){/*输入n个矩阵*/
         for(int j = 1 ; j <= m ; j++){
           for(int k = 1 ; k <= m ; k++)
              scanf("%d" , &c[i].matrix[j][k]);
         }
      }
      solve();/*判断点之间是否连通*/
      floyd();
      scanf("%d" , &k);
      for(int i = 0 ; i < k ; i++){
          scanf("%d%d" , &star , &end);
          if(dis[star][end] == INF)
            printf("Sorry\n");
          else
            printf("%lld\n" , dis[star][end]);
      }
   }
   return 0;
}