POJ3613 Cow Relays

题意：给定一个T(2 <= T <= 100)条边的无向图，求S到E恰好经过N(2 <= N <= 1000000)条边的最短路。

分析：

这应该是本周作业题里最难的一道题了，本蒟蒻只想到了dp做法，f(i, j, k)表示i到j经过k条边的最短路，f(i, j, k) = min(f(i, o, k-1) + edge(o, j).w)，不用说，一看就超时。

今天听完zrt神犇的讲解后，顿时大彻大悟。

用一个矩阵a(i, j)来表示i到j经过若干条边的最短路，初始化a为i到j边的长度，没有则是正无穷。

然后重载*运算符，比如a矩阵表示经过n条边，b矩阵表示经过m条边，那么a * b得到的矩阵表示经过m + n条边，采用Floyd的思想进行更新。

为了省时间，用了快速幂，这样时间复杂度达到了O(n^3logk)，可以通过。

因为题目最多只有100条边，也就是200个点，但是数据中点的序号可能达到1000，所以进行了map在线离散化。

#include <cstdio>
#include <cstring>
#include <map>
using namespace std;

int K, n, m, s, t, x, y, z;
map<int, int> mp;

struct Matrix {
	int a[205][205];
	Matrix operator * (Matrix &r) {
		Matrix c;
		memset(c.a, 0x3f, sizeof c.a);
		for(int i = 1; i <= n; i++)
		for(int j = 1; j <= n; j++)
		for(int k = 1; k <= n; k++)
			c.a[i][j] = min(c.a[i][j], a[i][k] + r.a[k][j]);
		return c;
	}
}st, ans;

void power() {
	ans = st, K--;
	while(K) {
		if(K & 1) ans = ans * st;
		st = st * st;
		K >>= 1;
	}
}

int main() {
	scanf("%d%d%d%d", &K, &m, &s, &t);
	memset(st.a, 0x3f, sizeof st.a);
	while(m--) {
		scanf("%d%d%d", &z, &x, &y);
		if(mp[x]) x = mp[x]; else x = mp[x] = ++n;
		if(mp[y]) y = mp[y]; else y = mp[y] = ++n;
		st.a[x][y] = st.a[y][x] = z;
	}
	power();
	printf("%d", ans.a[mp[s]][mp[t]]);
	return 0;
}

最后

以上就是小巧发夹为你收集整理的POJ3613 Cow Relays的全部内容，希望文章能够帮你解决POJ3613 Cow Relays所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。