|
|
Posted on 2011-05-02 17:39 Uriel 阅读(759) 评论(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;
}
|