当前位置:网站首页>AcWing 345. 牛站 题解(floyd的性质、倍增)
AcWing 345. 牛站 题解(floyd的性质、倍增)
2022-07-06 18:00:00 【乔大先生】
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;
}
边栏推荐
- json学习初体验–第三者jar包实现bean、List、map创json格式
- C language instance_ four
- 一起看看matlab工具箱内部是如何实现BP神经网络的
- Spark TPCDS Data Gen
- Installation and testing of pyflink
- How to evaluate load balancing performance parameters?
- curl 命令
- 【信号与系统】
- Yunna | work order management software, work order management software app
- Dark horse notes - create immutable sets and streams
猜你喜欢
AI automatically generates annotation documents from code
黑马笔记---创建不可变集合与Stream流
Analysis of mutex principle in golang
tansig和logsig的差异,为什么BP喜欢用tansig
第三方跳转网站 出现 405 Method Not Allowed
Go zero micro service practical series (IX. ultimate optimization of seckill performance)
Send template message via wechat official account
Transplant DAC chip mcp4725 to nuc980
go-zero微服务实战系列(九、极致优化秒杀性能)
微信公众号发送模板消息
随机推荐
Dark horse notes - create immutable sets and streams
Implementation principle of waitgroup in golang
Transformation transformation operator
How to manage distributed teams?
THREE.AxesHelper is not a constructor
云呐|工单管理办法,如何开展工单管理
NEON优化:矩阵转置的指令优化案例
Add the applet "lazycodeloading": "requiredcomponents" in taro,
Neon Optimization: summary of performance optimization experience
2022 Google CTF SEGFAULT LABYRINTH wp
黑马笔记---创建不可变集合与Stream流
从零开始匹配vim(0)——vimscript 简介
7.6模拟赛总结
修改px4飞控的系统时间
字节P7专业级讲解:接口测试常用工具及测试方法,福利文
安全保护能力是什么意思?等保不同级别保护能力分别是怎样?
[chip scheme design] pulse oximeter
Google发布安全更新,修复Chrome中已被利用的0 day
[case sharing] basic function configuration of network loop detection
Let's see through the network i/o model from beginning to end