| |
|
开发:
C++知识库
Java知识库
JavaScript
Python
PHP知识库
人工智能
区块链
大数据
移动开发
嵌入式
开发工具
数据结构与算法
开发测试
游戏开发
网络协议
系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程 数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁 |
-> 数据结构与算法 -> [离散化][倍增][floyd变形]牛站 AcWing345 -> 正文阅读 |
|
[数据结构与算法][离散化][倍增][floyd变形]牛站 AcWing345 |
?给定一张由?T?条边构成的无向图,点的编号为 1~1000?之间的整数。 求从起点?S?到终点?E?恰好经过?N?条边(可以重复经过)的最短路。 注意: 数据保证一定有解。 输入格式 第?1?行:包含四个整数 N,T,S,E。 第 2..T+1?行:每行包含三个整数,描述一条边的边长以及构成边的两个点的编号。 输出格式 输出一个整数,表示最短路的长度。 数据范围 2≤T≤100, 输入样例:
输出样例:
题意:? 给出一张包含n个点m条边的无向图,求从s到t恰好经过T条边的最短路。 分析:? 这道题可以用类似floyd的思想处理,假如已经得到了从i到j恰好经过T-1条边的最短路(任取t小于T),那从i到j恰好经过T条边就可以通过枚举中间点k来求得。所以可以用四重循环解决,最外层枚举恰好经过的边数t,内三层跑一个floyd变形,设dis[i][j]含义为在恰好经过t条边的情况下,从i点到j点的最短距离,这样有状态转移方程temp[i][j] = min(temp[i][j], dis[i][k]+mp[k][j]),dis[i][j] = temp[i][j],用temp是为了防止过程中改变dis的值。不过这种做法时间复杂度为O(T*n^3),显然会超时,于是接下来考虑优化方法。 在内层floyd的过程中,可以发现dis值的更新是存在结合律的,也就是说从i点到j点恰好经过t条边的最短路可以拆分为经过t/2和t/2条边的最短路之和,这样就有了倍增的基础,而且存在结合律就可以用快速幂来处理。实际的代码实现也是类似快速幂的,只是把快速幂中的乘法写成了一次floyd变形,时间复杂度为O(logT*n^3)。 这道题还有一些细节。关于ans数组初值设置以及dis数组(代码中为base数组)初值设置。dis数组应该初始化为只有1条边时的最短距离,特别需要注意的是到自身的dis值不能设置为0,否则就相当于每个点都引入了一条边权为0的自环,这是不符合题意的。ans数组相当于快速幂中的base^0,也就是恰好经过0条边时的最短距离,这里到自身的最短距离要置0,这是为了保证第一次遇到power为奇数的情况时能够把ans数组赋值为base数组,就像快速幂中那样。最后还需要离散化一下点,因为点的编号为1~1000,这么多点跑一次floyd就会超时,同时注意到最多只有100条边,因此必须要离散化一下。 具体代码如下:
|
|
|
上一篇文章 下一篇文章 查看所有文章 |
|
开发:
C++知识库
Java知识库
JavaScript
Python
PHP知识库
人工智能
区块链
大数据
移动开发
嵌入式
开发工具
数据结构与算法
开发测试
游戏开发
网络协议
系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程 数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁 |
360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年11日历 | -2024/11/26 13:44:36- |
|
网站联系: qq:121756557 email:121756557@qq.com IT数码 |