POJ 3613 Cow Relays

题目大意：起点到终点经过边的数目为k的最短路值为多少。

离散数学的定理：

01邻接矩阵A的K次方C=A^K,C[i][j]表示i点到j点正好经过K条边的路径数

对应于这道题,对邻接图进行K次floyd之后,C[i][j]就是点i到j正好经过K条边的最短路。

但是每次floyd的复制度十分大，所以我们需要使用矩阵快速幂。

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=210,inf=0x3f3f3f3f;
int n,t,s,e,cnt,g[N][N],a[N][N];
unordered_map<int,int> mp;
void mul(int a[][N],int b[][N]){
	int p[N][N]; memset(p,inf,sizeof p);
	for(int k=1;k<=cnt;k++)
		for(int i=1;i<=cnt;i++)
			for(int j=1;j<=cnt;j++)
				p[i][j]=min(p[i][j],a[i][k]+b[k][j]);
	for(int i=1;i<=cnt;i++)	for(int j=1;j<=cnt;j++)	a[i][j]=p[i][j];
}
void qmi(int b){
	for(int i=1;i<=cnt;i++)	for(int j=1;j<=cnt;j++)	a[i][j]=g[i][j];
	while(b){
		if(b&1)	mul(g,a); b>>=1; mul(a,a);
	}
}
signed main(){
	cin>>n>>t>>s>>e;	memset(g,inf,sizeof g);
	while(t--){
		int u,v,w;	cin>>w>>u>>v;
		if(!mp[u])	mp[u]=++cnt;
		if(!mp[v])	mp[v]=++cnt;
		g[mp[u]][mp[v]]=g[mp[v]][mp[u]]=min(g[mp[u]][mp[v]],w);
	}
	qmi(n-1);
	cout<<g[mp[s]][mp[e]]<<endl;
	return 0;
}