|
Posted on 2011-05-02 17:39 Uriel 阅读(753) 评论(0) 编辑 收藏 引用 所属分类: POJ 、 图论
这是在DY大牛第六期专题里列出的题目之一.
话说搞ACM也2年多了, 竟然用矩阵乘法+Floyd的题目都还没有做过... 上周的组队赛遇到一道题才听说... (没有拜读matrix67的神文... 检讨下... )
/**//* POJ 3613 Cow Relays
-------Classify: Floyd+矩阵乘法 ----Description: 求从S到T恰好经过K条边(可重复走)的最短路 -----------------K<=1e6, m<100(边数) ---Sample Input:
2 6 6 4----------//K m s t 11 4 6-----------//length x<->y 4 4 8 8 4 9 6 6 8 2 6 9 3 8 9
--Sample Output:
10
-----Time Limit: 1000Ms ---------Source: USACO 2007 November Gold -------Solution:
By Solution Report
01邻接矩阵A的K次方C=A^K,C[i][j]表示i点到j点正好经过K条边的路径数
对应于这道题,对邻接图进行K次floyd之后,C[i][j]就是点i到j正好经过K条边的最短路
---------Status: AC C++ 532Ms -----------Date: 2011.05.02 ------Reference: http://hi.baidu.com/aconly/blog/item/23fb73acc1d874004b36d634.html -----------Code: */
#include<stdio.h> #include<stdlib.h> #include<string.h> #define N 1010 #define INF 0x3f3f3f3f typedef int M[N][N];
int k, m, s, t, v; int ans[N][N], adj[N][N], vis[N], vtx[N], dis[N][N], tp[N][N];
void floyd(M c, M a, M b) { int i, j, k; for (k = 0; k < v; ++k) for (i = 0; i < v; ++i) for (j = 0; j < v; ++j) if (c[vtx[i]][vtx[j]] > a[vtx[i]][vtx[k]] + b[vtx[k]][vtx[j]]) c[vtx[i]][vtx[j]] = a[vtx[i]][vtx[k]] + b[vtx[k]][vtx[j]]; }
void copy(M a, M b) { int i, j; for (i = 0; i < v; ++i) for (j = 0; j < v; ++j) { a[vtx[i]][vtx[j]] = b[vtx[i]][vtx[j]]; b[vtx[i]][vtx[j]] = INF; } }
void BS(int k) { while (k) { if (k & 1) { floyd(dis, ans, adj); copy(ans, dis); } floyd(tp, adj, adj); copy(adj, tp); k >>= 1; } }
int main() { int i, j, x, y, w; scanf("%d %d %d %d", &k, &m, &s, &t); for (i = 0; i <= 1001; ++i) { for (j = 0; j <= 1001; ++j) { adj[i][j] = INF; tp[i][j] = INF; dis[i][j] = INF; ans[i][j] = INF; } ans[i][i] = 0; } v = 0; memset(vis, 0, sizeof(vis)); for (i = 0; i < m; ++i) { scanf("%d %d %d", &w, &x, &y); if (!vis[x]) { vis[x] = 1; vtx[v++] = x; } if (!vis[y]) { vis[y] = 1; vtx[v++] = y; } if (adj[x][y] > w) adj[x][y] = adj[y][x] = w; } BS(k); printf("%d\n", ans[s][t]); return 0; }
|