首页 > 代码库 > BZOJ 1706 usaco 2007 Nov relays 奶牛接力跑/POJ 3613 Cow Relays 倍增Floyd
BZOJ 1706 usaco 2007 Nov relays 奶牛接力跑/POJ 3613 Cow Relays 倍增Floyd
题目大意:求恰好走k步从S到T的最短路。
思路:设f[p][i][j]为从i到j恰好走2^p步的最短路,DP方程十分简单:f[p][i][j] = min(f[p][i][j],f[p - 1][i][k] + f[p - 1][k][j]);
对总步数T进行二进制拆分,在T有1的位置上,假如这个位置为p,那么就用f[p][][]来更新答案g[][],最后得到的g[][]就是答案矩阵。
注意要离散化一下。。
CODE:
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define MAX 210 using namespace std; #define min(a,b) ((a) < (b) ? (a):(b)) #define max(a,b) ((a) > (b) ? (a):(b)) struct Complex{ int x,y,len; void Read() { scanf("%d%d%d",&len,&x,&y); } }edge[MAX]; pair<int,int *> xx[1010]; int cnt,t; int T,edges,points,start,end; int f[20][MAX][MAX],g[MAX][MAX],h[MAX][MAX]; int main() { cin >> T >> edges >> start >> end; memset(g,0x3f,sizeof(g)); memset(f,0x3f,sizeof(f)); for(int i = 1; i <= edges; ++i) { edge[i].Read(); xx[++cnt].first = edge[i].x,xx[cnt].second = &edge[i].x; xx[++cnt].first = edge[i].y,xx[cnt].second = &edge[i].y; } xx[++cnt].first = start,xx[cnt].second = &start; xx[++cnt].first = end,xx[cnt].second = &end; sort(xx + 1,xx + cnt + 1); for(int i = 1; i <= cnt; ++i) { if(i == 1 || xx[i].first != xx[i - 1].first) ++t; *xx[i].second = t; } for(int i = 1; i <= edges; ++i) f[0][edge[i].x][edge[i].y] = f[0][edge[i].y][edge[i].x] = min(f[0][edge[i].x][edge[i].y],edge[i].len); points = t; for(int i = 1; i <= points; ++i) g[i][i] = 0; int p = 0; while(T) { if(T&1) { memset(h,0x3f,sizeof(h)); for(int k = 1; k <= points; ++k) for(int i = 1; i <= points; ++i) for(int j = 1; j <= points; ++j) h[i][j] = min(h[i][j],g[i][k] + f[p][k][j]); memcpy(g,h,sizeof(g)); } T >>= 1; ++p; for(int k = 1; k <= points; ++k) for(int i = 1; i <= points; ++i) for(int j = 1; j <= points; ++j) f[p][i][j] = min(f[p][i][j],f[p - 1][i][k] + f[p - 1][k][j]); } cout << g[start][end] << endl; return 0; }
BZOJ 1706 usaco 2007 Nov relays 奶牛接力跑/POJ 3613 Cow Relays 倍增Floyd
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。