设为首页 加入收藏

TOP

POJ 3613 Cow Relays （floyd + 矩阵快速幂）
2015-07-24 05:57:28 来源: 作者: 【大 中 小】 浏览:5次
Tags：POJ 3613 Cow Relays floyd 矩阵 快速

题目大意：

求刚好经过K条路的最短路



我们知道如果一个矩阵A[i][j] 表示表示 i-j 是否可达

那么 A*A=B B[i][j] 就表示 i-j 刚好走过两条路的方法数


那么同理

我们把i-j 的路径长度存到A 中。

在A*A的过程中，不断取小的，那么最后得到的也就是i - j 走过两条路的最短路了。

当然也是利用到了floyd的思想。

然后要求出K次的最短路，那么就是矩阵快速幂的工作了。

注意要离散化。用map

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
       using namespace std; const int N = 101; map
       
        mymap; struct matrix { int a[N][N]; }temp,res,origin; int n; matrix mul(matrix x,matrix y) { memset(temp.a,0x3f,sizeof temp.a); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) for(int k=1;k<=n;k++) temp.a[i][j]=min(temp.a[i][j],x.a[i][k]+y.a[k][j]); return temp; } matrix matmod(matrix A,int k) { memset(res.a,0x3f,sizeof res.a); for(int i=1;i<=n;i++)res.a[i][i]=0; while(k) { if(k&1)res=mul(res,A); A=mul(A,A); k>>=1; } return res; } int main() { int k,m,s,e; while(scanf("%d%d%d%d",&k,&m,&s,&e)!=EOF) { memset(origin.a,0x3f,sizeof(origin.a)); mymap.clear(); int num=0; for(int i=0;i
【大 中 小】【打印】 【繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部】
分享到: 
上一篇：求树中两个节点的最低公共祖先 下一篇：HDU1236 排名 题解

评论

帐　　号: 密码: (新用户注册)
验 证 码:
表　　情:
内　　容: