)
信奥赛C++提高组csp-s之倍增算法思想及应用案例(3)
题目描述
小 A 的工作不仅繁琐，更有苛刻的规定，要求小 A 每天早上在6 : 00 6:006:00之前到达公司，否则这个月工资清零。可是小 A 偏偏又有赖床的坏毛病。于是为了保住自己的工资，小 A 买了一个空间跑路器，每秒钟可以跑2 k 2^k2k千米（k kk是任意自然数）。当然，这个机器是用longint存的，所以总跑路长度不能超过maxlongint千米。小 A 的家到公司的路可以看做一个有向图，小 A 家为点1 11，公司为点n nn，每条边长度均为一千米。小 A 想每天能醒地尽量晚，所以让你帮他算算，他最少需要几秒才能到公司。数据保证1 11到n nn至少有一条路径。
输入格式
第一行两个整数n , m n,mn,m，表示点的个数和边的个数。
接下来m mm行每行两个数字u , v u,vu,v，表示一条u uu到v vv的边。
输出格式
一行一个数字，表示到公司的最少秒数。
输入输出样例 #1
输入 #1
4 4 1 1 1 2 2 3 3 4输出 #1
1说明/提示
【样例解释】
1 → 1 → 2 → 3 → 4 1 \to 1 \to 2 \to 3 \to 41→1→2→3→4，总路径长度为4 44千米，直接使用一次跑路器即可。
【数据范围】
50 % 50\%50%的数据满足最优解路径长度≤ 1000 \leq 1000≤1000；
100 % 100\%100%的数据满足2 ≤ n ≤ 50 2\leq n \leq 502≤n≤50，m ≤ 10 4 m \leq 10 ^ 4m≤104，最优解路径长度≤ \leq≤maxlongint。
AC代码
#include<bits/stdc++.h>usingnamespacestd;constintN=60;// 最大节点数constintLOG=62;// 最大对数，2^62足够大intn,m;boolg[N][N][LOG];// g[i][j][k] 表示是否存在从i到j长度为2^k的路径intd[N][N];// d[i][j] 表示从i到j的最短时间（秒数）intmain(){cin>>n>>m;// 初始化memset(g,false,sizeof(g));memset(d,0x3f,sizeof(d));// 初始化为无穷大// 读入边信息for(inti=1;i<=m;i++){intu,v;cin>>u>>v;g[u][v][0]=true;// 基础边，长度为2^0=1d[u][v]=1;// 直接边需要1秒}// 倍增预处理：计算所有2^k可达性for(intk=1;k<LOG;k++){// 处理2^k长度for(intt=1;t<=n;t++){// 中间点for(inti=1;i<=n;i++){// 起点for(intj=1;j<=n;j++){// 终点// 如果存在i->t的2^(k-1)路径和t->j的2^(k-1)路径// 那么存在i->j的2^k路径if(g[i][t][k-1]&&g[t][j][k-1]){g[i][j][k]=true;d[i][j]=1;// 2^k路径只需要1秒}}}}}// Floyd算法计算最短时间for(intk=1;k<=n;k++){// 中间点for(inti=1;i<=n;i++){// 起点for(intj=1;j<=n;j++){// 终点// 更新最短时间d[i][j]=min(d[i][j],d[i][k]+d[k][j]);}}}cout<<d[1][n]<<endl;// 输出从1到n的最短时间return0;}功能分析
问题理解
- 跑路器特性：每秒可以跑2 k 2^k2k千米（k kk是任意自然数）
- 图结构：有向图，每条边长度为1千米
- 目标：计算从节点1到节点n的最少秒数
算法思想
倍增预处理：
g[i][j][k] = true表示存在从i到j长度为2 k 2^k2k的路径- 通过动态规划计算：如果存在i→t的2 k − 1 2^{k-1}2k−1路径和t→j的2 k − 1 2^{k-1}2k−1路径，那么存在i→j的2 k 2^k2k路径
- 对于这样的路径，设置
d[i][j] = 1（因为一次跑路器就能走完）
Floyd算法：
- 在预处理的基础上，计算任意两点间的最短时间
- 考虑通过中间点的路径组合，找到真正的最短时间
关键点说明
为什么需要两步处理：
- 第一步找出所有可以用1秒到达的点对（距离为2的幂次）
- 第二步组合这些1秒路径，找到最优的路径序列
时间复杂度：
- 倍增预处理：O(n³ × LOG)
- Floyd算法：O(n³)
- 由于n≤50，这在可接受范围内
示例解释
对于样例：
4 4 1 1 1 2 2 3 3 4- 存在路径1→1→2→3→4，总长度4千米
- 4是2的幂次（4=2²），所以一次跑路器即可
- 输出1
更多系列知识，请查看专栏：《信奥赛C++提高组csp-s知识详解及案例实践》：
https://blog.csdn.net/weixin_66461496/category_13113932.html
各种学习资料，助力大家一站式学习和提升！！！
#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"########## 一站式掌握信奥赛知识! ##########";cout<<"############# 冲刺信奥赛拿奖! #############";cout<<"###### 课程购买后永久学习，不受限制! ######";return0;}1、csp信奥赛高频考点知识详解及案例实践：
CSP信奥赛C++动态规划：
https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转
CSP信奥赛C++标准模板库STL：
https://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转
信奥赛C++提高组csp-s知识详解及案例实践：
https://blog.csdn.net/weixin_66461496/category_13113932.html
2、csp信奥赛冲刺一等奖有效刷题题解：
CSP信奥赛C++初赛及复赛高频考点真题解析（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转
CSP信奥赛C++一等奖通关刷题题单及题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转
3、GESP C++考级真题题解：
GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转
GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转
GESP(C++ 七级+八级)真题题解（持续更新）：
https://blog.csdn.net/weixin_66461496/category_13117178.html
4、CSP信奥赛C++竞赛拿奖视频课：
https://edu.csdn.net/course/detail/40437 点击跳转
· 文末祝福 ·
#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;})
)
)
