AcWing 345. 牛站 题解（floyd的性质、倍增）

AcWing 345. 牛站
解题思路：本体所用的floyd和求最短路的floyd本质不同，虽然都是三重循环，但本题中的d[k][i]j]表示的是由i~j经过k条边的最短距离，在确定这个之后，进一步推d[a+b][i][j] = min(d[a+b][i][j]，d[a][i]k] + d[b][k][j]），由于d[a][i]k] 和 d[b][k][j]之间不相互影响，所以可以联想出由快速幂得到最短距离

大老远题解

#include<bits/stdc++.h>

using namespace std;

const int N = 210;

map<int, int>mp;
int n, m, S, E, k;
int g[N][N];  //g[i][j]储存i~j经过一条边的最短距离 
int res[N][N];  //储存经过快速幂之后经过k次循环即k条边的值

void mul(int c[][N], int a[][N], int b[][N]){
    
	static int temp[N][N];//新建一个数组，使状态不会被继承
	memset(temp, 0x3f, sizeof temp);
	for(int k = 1; k <= n; k ++ ){
    
		for(int i = 1; i <= n; i ++ ){
    
			for(int j = 1; j <= n; j ++ ){
    
				temp[i][j] = min(temp[i][j], a[i][k] + b[k][j]);
			}
		}
	}
	memcpy(c, temp, sizeof temp);
} 

void qmi(){
      //快速幂 
	memset(res, 0x3f, sizeof res);  //初始化数组（相当于初始化距离数组）
	for(int i = 1; i <= n; i ++ ) res[i][i] = 0;  //res是最短距离，所以要初始化为0
	//res[x][y]记录的是x到y的距离，循环过k次之后就是经过k条边的距离 
	while(k){
      //第一次循环经过一条边，第二次循环经过两条边，第k次循环就是经过k条边
		if(k & 1) mul(res, res, g);  // res = res * g 
		mul(g, g, g);  // g = g * g 让g数组身上的权重不断累加1->2->4->8 
		k >>= 1; 
	}
}

int main()
{
    
	cin>>k>>m>>S>>E;
	//图中共有m条边，从起点S到终点E，经过k条可重复边的最短路径 
	memset(g, 0x3f, sizeof g);  //g是确定至少有一条路可走的最短距离，所以不初始化为0
	//对起点、终点离散化
	if(!mp.count(S)) mp[S] = ++ n;
	if(!mp.count(E)) mp[E] = ++ n;
	S = mp[S], E = mp[E];	 
	
	while(m -- ){
    
		int a, b, c;
		cin>>c>>a>>b;
		if(!mp.count(a)) mp[a] = ++ n;
		if(!mp.count(b)) mp[b] = ++ n;
		a = mp[a], b = mp[b];
		g[a][b] = g[b][a] = min(g[a][b], c);  //g[x][y]在这里记录的是从x到y经过一条边记录的距离 
	}
	
	qmi();
	
	cout<<res[S][E]<<endl;
	return 0;
}