AcWing 345. Cattle station solution (nature and multiplication of Floyd)

AcWing 345. Niu station
Their thinking ： Used by the body floyd And find the shortest floyd Different in nature , Although they are all triple cycles , But in this question d[k][i]j] Indicates that the i~j after k The shortest distance of the edge , After confirming this , Further push d[a+b][i][j] = min(d[a+b][i][j],d[a][i]k] + d[b][k][j]）, because d[a][i]k] and d[b][k][j] They do not interact with each other , So we can think of the shortest distance obtained by fast power

Far away solution

#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] Store i~j The shortest distance across an edge  
int res[N][N];  // After fast exponentiation, storage passes k This cycle is k Value of the edge 

void mul(int c[][N], int a[][N], int b[][N]){
    
	static int temp[N][N];// Create a new array , Make the state not inherited 
	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(){
      // Fast power  
	memset(res, 0x3f, sizeof res);  // Initialize array （ Equivalent to initializing the distance array ）
	for(int i = 1; i <= n; i ++ ) res[i][i] = 0;  //res It's the shortest distance , So initialize to 0
	//res[x][y] The record is x To y Distance of , Cycle through k After times, it will pass k The distance between the edges  
	while(k){
      // The first cycle passes through an edge , The second cycle passes through two sides , The first k The second cycle is through k side 
		if(k & 1) mul(res, res, g);  // res = res * g 
		mul(g, g, g);  // g = g * g  Give Way g The weight on the array keeps accumulating 1->2->4->8 
		k >>= 1; 
	}
}

int main()
{
    
	cin>>k>>m>>S>>E;
	// The graph contains m side , From the starting point S To the end point E, after k The shortest path of repeatable edges  
	memset(g, 0x3f, sizeof g);  //g It is the shortest distance to determine that there is at least one way to go , So it is not initialized to 0
	// Right starting point 、 End point discretization 
	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] What is recorded here is from x To y The distance recorded through an edge  
	}
	
	qmi();
	
	cout<<res[S][E]<<endl;
	return 0;
}