POJ 3613 Cow Relays-白红宇

POJ 3613 Cow Relays

阅读量：7110 次

发布时间：2019-06-28

本文共 1116 字，大约阅读时间需要 3 分钟。

题意：求经过K条边 S和E点之间的最短路。

思路：floyd通过一个点k去更新i j两点的距离。那么N-1次floyd则通过N-1个点来更新i j之间的距离那么在i j中间恰好N条边。

首先需要离散化点。然后用类似于快速幂的方法进行floyd，把加的操作换成松弛操作。

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           using namespace std;const int INF=0x3f3f3f3f;const int MAXN=110;map
            
              Map;int N,T,S,E;struct Matrix{ int m[MAXN][MAXN]; Matrix() { memset(m,-1,sizeof(m)); }};Matrix mtMul(Matrix A, Matrix B){ int i, j, k, tmp; Matrix C; for(i = 0; i < Map.size(); i ++) for(j = 0; j < Map.size(); j ++) for(k = 0; k < Map.size(); k ++) { if(A.m[i][k] == -1 || B.m[k][j] == -1) continue; tmp = A.m[i][k] + B.m[k][j]; if(C.m[i][j] == -1 || C.m[i][j] > tmp) C.m[i][j] = tmp; } return C;}Matrix mtPow(Matrix A, int k){ if(k == 1) return A; Matrix B = mtPow(A, k / 2); if(k % 2 == 0) return mtMul(B, B); else return mtMul(mtMul(B, B), A);}int main(){ while(scanf("%d%d%d%d",&N,&T,&S,&E)!=EOF) { int cnt=0; Map.clear(); int u,v,w; Matrix G; for(int i=0;i