首页 > 代码库 > BZOJ 1706 usaco2007 Nov relays 奶牛接力跑 倍增Floyd
BZOJ 1706 usaco2007 Nov relays 奶牛接力跑 倍增Floyd
题目大意:给定一张无向图,求从s出发恰好经过n条边到达e的最短路
倍增Floyd……为何大家都管这个叫做矩阵乘法- - 算了为何要纠结这种事- -
令f[p][i][j]表示走2^p步从i到达j的最短路 有f[p][i][j]=min{f[p-1][i][k]+f[p-1][k][j]}
将n进行二进制拆分 用矩阵g记录答案矩阵 对于每一位p 用f[p]和g两个矩阵搞出h 再将h的值赋给g
切忌直接用f[p]更新g 这样可能导致g的上一次的值被继承到下一次里 这样相当于这一步没跑
100条边,因此最多200个点,离散化一下就行了
这编号真是反人类- -
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define M 220 using namespace std; struct abcd{ int x,y,z; }edges[110]; int n,t,s,e,tot; int f[M][M],g[M][M],h[M][M]; pair<int,int*> b[M<<1]; void Initialize() { memset(f,0x3f,sizeof f); memset(h,0x3f,sizeof h); for(int i=1;i<=tot;i++) h[i][i]=0; } int main() { int temp,i,j,k; cin>>n>>t>>s>>e; for(i=1;i<=t;i++) { scanf("%d%d%d",&edges[i].z,&edges[i].x,&edges[i].y); b[i+i-1]=make_pair(edges[i].x,&edges[i].x); b[i<<1]=make_pair(edges[i].y,&edges[i].y); } b[i+i-1]=make_pair(s,&s); b[i<<1]=make_pair(e,&e); sort(b+1,b+t+t+3); for(i=1;i<=t+1<<1;i++) { if(i==1||b[i].first!=b[i-1].first) ++tot; *b[i].second=tot; } Initialize(); for(i=1;i<=t;i++) f[edges[i].x][edges[i].y]=f[edges[i].y][edges[i].x]=edges[i].z; for(temp=0;(1<<temp)<=n;temp++) { if( n&(1<<temp) ) { memset(g,0x3f,sizeof g); for(k=1;k<=tot;k++) for(i=1;i<=tot;i++) for(j=1;j<=tot;j++) g[i][j]=min(g[i][j],f[i][k]+h[k][j]); memcpy(h,g,sizeof h); } memset(g,0x3f,sizeof g); for(k=1;k<=tot;k++) for(i=1;i<=tot;i++) for(j=1;j<=tot;j++) g[i][j]=min(g[i][j],f[i][k]+f[k][j]); memcpy(f,g,sizeof f); } cout<<h[s][e]<<endl; return 0; }
BZOJ 1706 usaco2007 Nov relays 奶牛接力跑 倍增Floyd
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。