当前位置:网站首页>AcWing 345. Cattle station solution (nature and multiplication of Floyd)
AcWing 345. Cattle station solution (nature and multiplication of Floyd)
2022-07-07 01:36:00 【Mr. Qiao Da】
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;
}
边栏推荐
- swiper组件中使用video导致全屏错位
- 今日问题-2022/7/4 lambda体中修改String引用类型变量
- 2022 Google CTF SEGFAULT LABYRINTH wp
- ClickHouse字段分组聚合、按照任意时间段粒度查询SQL
- AcWing 361. 观光奶牛 题解(spfa求正环)
- Transformation transformation operator
- shell脚本快速统计项目代码行数
- Google released a security update to fix 0 days that have been used in chrome
- Set WordPress pseudo static connection (no pagoda)
- 【信号与系统】
猜你喜欢
Let's see how to realize BP neural network in Matlab toolbox
Start from the bottom structure to learn the customization and testing of fpga---- FIFO IP
AI automatically generates annotation documents from code
【信号与系统】
Gazebo的安装&与ROS的连接
Appium foundation - appium inspector positioning tool (I)
2022 Google CTF SEGFAULT LABYRINTH wp
云呐|工单管理软件,工单管理软件APP
js如何快速创建一个长度为 n 的数组
黑马笔记---异常处理
随机推荐
THREE. AxesHelper is not a constructor
Go zero micro service practical series (IX. ultimate optimization of seckill performance)
子网划分、构造超网 典型题
Js逆向——捅了【马蜂窝】的ob混淆与加速乐
Asset security issues or constraints on the development of the encryption industry, risk control + compliance has become the key to breaking the platform
454-百度面经1
405 method not allowed appears when the third party jumps to the website
AcWing 904. 虫洞 题解(spfa求负环)
Machine learning: the difference between random gradient descent (SGD) and gradient descent (GD) and code implementation.
JS reverse -- ob confusion and accelerated music that poked the [hornet's nest]
Transformation transformation operator
C语言实例_5
黑马笔记---创建不可变集合与Stream流
Today's question -2022/7/4 modify string reference type variables in lambda body
Typical problems of subnet division and super network construction
剑指 Offer II 035. 最小时间差-快速排序加数据转换
7.6模拟赛总结
Wood extraction in Halcon
7.6 simulation summary
Byte P7 professional level explanation: common tools and test methods for interface testing, Freeman