【POJ3613 Cow Relays】（广义矩阵乘法）

题目链接

先离散化，假设有$P$个点

定义矩阵$A_{ij}$表示$i$到$j$只经过一条边的最短路，$${(A^{a+b}){ij}=\min{1\le k\le p} { (A^a)_{ik}+(Ab)_{kj} }}$$

$A^{a+b}_{ij}$表示$i$到$j$经过$(a+b)$条边的最短路。

这不就是$ddp$里常用的广义矩阵乘法吗，直接上快速幂即可。

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

int b[1010], n, m, s, t, cnt, A, B, C;

struct Matrix{

	int a[220][220];

}M;

Matrix operator * (Matrix a, Matrix b){

	Matrix c;

	for(int i = 1; i <= cnt; ++i)

		for(int j = 1; j <= cnt; ++j){

			c.a[i][j] = 1 << 29;

			for(int k = 1; k <= cnt; ++k)

				c.a[i][j] = min(c.a[i][j], a.a[i][k] + b.a[k][j]);

		}

	return c;

}

int main(){

	scanf("%d%d%d%d", &n, &m, &s, &t);

	memset(M.a, 63, sizeof M.a);

	for(int i = 1; i <= m; ++i){

		scanf("%d%d%d", &C, &A, &B);

		if(!b[A]) b[A] = ++cnt;

		if(!b[B]) b[B] = ++cnt;

		M.a[b[A]][b[B]] = M.a[b[B]][b[A]] = C;

	}

	Matrix now = M; --n;

	while(n){

		if(n & 1) now = now * M;

		M = M * M; n >>= 1;

	}

	printf("%d\n", now.a[b[s]][b[t]]);

	return 0;

}

巴特西

【POJ3613 Cow Relays】（广义矩阵乘法）

最新文章

热门文章