|
|
Posted on 2011-05-02 17:39 Uriel 閱讀(776) 評(píng)論(0) 編輯 收藏 引用 所屬分類: POJ 、 圖論
這是在DY大牛第六期專題里列出的題目之一.
話說(shuō)搞ACM也2年多了, 竟然用矩陣乘法+Floyd的題目都還沒有做過(guò)... 上周的組隊(duì)賽遇到一道題才聽說(shuō)... (沒有拜讀matrix67的神文... 檢討下... )
  /**//*
 POJ 3613 Cow Relays
-------Classify: Floyd+矩陣乘法
----Description: 求從S到T恰好經(jīng)過(guò)K條邊(可重復(fù)走)的最短路
-----------------K<=1e6, m<100(邊數(shù))
---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點(diǎn)到j(luò)點(diǎn)正好經(jīng)過(guò)K條邊的路徑數(shù)
對(duì)應(yīng)于這道題,對(duì)鄰接圖進(jìn)行K次floyd之后,C[i][j]就是點(diǎn)i到j(luò)正好經(jīng)過(guò)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;
}
|