「POJ3613」Cow Relays

题意：

一张 $T$ 条边的无向图，点的编号为从 $1\sim 1000$，求从起点 $S$ 到终点 $E$ 恰好经过 $N$ 条边(可以重复)的最短路。

虽然点为从 $1\sim 1000$，但是边只有 $100$ 条，所以可以先离散化点的编号为 $1\sim P$。

离散化后，用邻接矩阵 $A$ 存储边，所以 $A[i,j]$ 代表从 $i$ 到 $j$ 只经过一条边时的最短路。

由 $Floyd$ 的方程可知，$d[i,j]=d[i,k]+d[k,j]$，表示经过中转点 $k$ ，从 $i$ 到 $j$，所以这时代表经过两条边的最短路。

设矩阵 $A^m$ 代表两点间经过 $m$ 条边的最短路，所以我们可以由 $Floyd$ 引申得到：

$$(A^{r+m})[i,j]=\mathop{min}\limits_{1\leq k\leq P}((A^r)[i,k]+(A^m)[k,j])$$

可以发现，上式其实是一个关于 $min$ 和加法运算的矩阵乘法式子，所以可以直接快速幂算出 $A^N$。只用把矩阵乘法中的乘法用加法代替，加法用 $min$ 代替。

最后，$A^N[S,E]$ 即为答案。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
int n,t,s,e;
struct matrix
{
	int a[510][510];
}ans,x,now;
int l[1010101],cnt;
matrix multi(matrix u,matrix v)
{
	matrix w;
	memset(w.a,0x3f,sizeof(w.a));
	for(int k=1;k<=cnt;k++)
		for(int i=1;i<=cnt;i++)
			for(int j=1;j<=cnt;j++)
				w.a[i][j]=min(w.a[i][j],u.a[i][k]+v.a[k][j]);
	return w;
}
void power()
{
	n--;
	ans=x;
	while(n)
	{
		if(n&1)
			ans=multi(ans,x);
		x=multi(x,x);
		n>>=1;
	}
}
int main()
{
	memset(x.a,0x3f,sizeof(x.a));
	scanf("%d%d%d%d",&n,&t,&s,&e);
	for(int i=1;i<=t;i++)
	{
		int r,b,c;
		scanf("%d%d%d",&r,&b,&c);
		if(!l[b])
			l[b]=++cnt;
		if(!l[c])
			l[c]=++cnt;
		x.a[l[b]][l[c]]=r;
		x.a[l[c]][l[b]]=r;
	}
	power();
	printf("%d",ans.a[l[s]][l[e]]);
	return 0;
}