AW345 牛站（广义矩阵乘法优化floyd）

题目地址

---

易错点：

• 由于是广义矩阵乘法，mul(Mat a,Mat b)方法中的局部变量ans不能使用memcpy直接复制矩阵a或b的数据.

---

#include<cstdio>
#include<iostream>
#include<cstring>
#include<map>
using namespace std;
const int MAXN=2e2;
struct Mat{
	int a[MAXN][MAXN];
	void pre(){
		memset(a,0x3f,sizeof(a));
	}
};
int nodeCnt=0;
Mat mul(Mat a,Mat b){
	Mat ans;
	ans.pre();
	for(int i=1;i<=nodeCnt;i++){
		for(int j=1;j<=nodeCnt;j++){
			for(int k=1;k<=nodeCnt;k++){
				ans.a[i][j]=min(ans.a[i][j],a.a[i][k]+b.a[k][j]);
			}
		}
	}
	return ans;
}
Mat poww(Mat a,int x){
	Mat ans;
	memcpy(ans.a,a.a,sizeof(ans.a));
	x--;
	while(x){
		if(x&1)ans=mul(ans,a);
		a=mul(a,a);
		x>>=1;
	}
	return ans;
}
map<int,int> m;
int main(){
	int n,t,s,e;
	scanf("%d%d%d%d",&n,&t,&s,&e);
	Mat a;//defult graph
	a.pre();
	for(int i=1;i<=t;i++){
		int u,v,w;
		scanf("%d%d%d",&w,&u,&v);
		u=m[u]?m[u]:(m[u]=++nodeCnt);
		v=m[v]?m[v]:(m[v]=++nodeCnt);
		a.a[u][v]=a.a[v][u]=min(a.a[u][v],w);
	}
	Mat ans=poww(a,n);
	printf("%d
",ans.a[m[s]][m[e]]);
	return 0;
}