fzuoj 2173(矩阵快速幂)-白红宇

fzuoj 2173(矩阵快速幂)

阅读量：6329 次

发布时间：2019-06-22

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

思路：用邻接矩阵存储图，然后矩阵的k次方即为答案。只需要修改矩阵乘法c[i][j] = min(c[i][j], a[i][k] + b[k][j])即可。并不难写关键是思路。

代码如下：

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #include 
           
             7 #include 
            
              8 #include 
              9 #include 
              
               10 #include 
               
                11 #include 
                
                 12 #include 
                 
                  13 using namespace std;14 15 const int LEN = 51;16 typedef long long ll;17 const ll LINF = 0x3f3f3f3f3f3f3f3fLL;18 int n, h, k;19 20 21 void debug(ll Mix[][LEN]){22 for(int i=0; i
                  
                   << Mix[i][j] << ' ' ;25 else cout << "- "; 26 }27 cout << endl;28 }cout << endl;29 }30 31 void Mul(ll a[][LEN], ll b[][LEN]){32 ll c[LEN][LEN];33 memset(c, 0x3f, sizeof c);34 for(int i=0; i
                   
                    >= 1;59 }60 for(int i=0; i
                    
                     > T;74 while(T--){75 memset(Mix, 0x3f, sizeof Mix);76 cin >> n >> h >> k;77 for(int i=0; i
                     
                      > a >> b >> val;79 a--, b--;80 Mix[a][b] = val; 81 }82 Mksm(Mix, k);83 if(Mix[0][n-1] != LINF) cout << Mix[0][n-1] << endl;84 else cout << -1 << endl;85 }86 return 0;87 }