企业官网建设流程全解析

如何增加网站的权重,深圳模板建站多少钱,辅导班,搭建网页步骤信奥赛C提高组csp-s之倍增算法思想及应用案例(3) 题目描述 小 A 的工作不仅繁琐#xff0c;更有苛刻的规定#xff0c;要求小 A 每天早上在 6:006:006:00 之前到达公司#xff0c;否则这个月工资清零。可是小 A 偏偏又有赖床的坏毛病。于是为了保住自己的工资#xff0c;小…信奥赛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输入 #14 4 1 1 1 2 2 3 3 4输出 #11说明/提示【样例解释】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≤1000100 % 100\%100%的数据满足2 ≤ n ≤ 50 2\leq n \leq 502≤n≤50m ≤ 10 4 m \leq 10 ^ 4m≤104最优解路径长度≤ \leq≤maxlongint。AC代码#includebits/stdc.husingnamespacestd;constintN60;// 最大节点数constintLOG62;// 最大对数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(){cinnm;// 初始化memset(g,false,sizeof(g));memset(d,0x3f,sizeof(d));// 初始化为无穷大// 读入边信息for(inti1;im;i){intu,v;cinuv;g[u][v][0]true;// 基础边长度为2^01d[u][v]1;// 直接边需要1秒}// 倍增预处理计算所有2^k可达性for(intk1;kLOG;k){// 处理2^k长度for(intt1;tn;t){// 中间点for(inti1;in;i){// 起点for(intj1;jn;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(intk1;kn;k){// 中间点for(inti1;in;i){// 起点for(intj1;jn;j){// 终点// 更新最短时间d[i][j]min(d[i][j],d[i][k]d[k][j]);}}}coutd[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的幂次42²所以一次跑路器即可输出1更多系列知识请查看专栏《信奥赛C提高组csp-s知识详解及案例实践》https://blog.csdn.net/weixin_66461496/category_13113932.html各种学习资料助力大家一站式学习和提升#includebits/stdc.husingnamespacestd;intmain(){cout########## 一站式掌握信奥赛知识! ##########;cout############# 冲刺信奥赛拿奖! #############;cout###### 课程购买后永久学习不受限制! ######;return0;}1、csp信奥赛高频考点知识详解及案例实践CSP信奥赛C动态规划https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转CSP信奥赛C标准模板库STLhttps://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转信奥赛C提高组csp-s知识详解及案例实践https://blog.csdn.net/weixin_66461496/category_13113932.html2、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.html4、CSP信奥赛C竞赛拿奖视频课https://edu.csdn.net/course/detail/40437 点击跳转· 文末祝福 ·#includebits/stdc.husingnamespacestd;intmain(){cout跟着王老师一起学习信奥赛C;cout 成就更好的自己 ;cout csp信奥赛一等奖属于你! ;return0;}