首页
比赛
题库
课程
竞赛讨论区
登录
/
注册
去牛客
首页
>
分层图最短路
3条解析
开通博客写题解
RainSure
发表于 2022-06-10 10:34:25
如果直接按照分层图最短路DP做法来搞的话,数组需要开成 dist[N][N], st[N][N], N是1e5级别的,明显会爆空间,那就直接给每两层之间的任意两点连一条边权为C的边,然后跑一遍最短路就好了。 代码(写的比较丑) #include<iostream> #include<
展开全文
在刷题的单身狗很开心
发表于 2023-11-07 16:51:48
直接建图利用最短路算法去搞。 这里首先说一下最短路的几种算法以及各自的用途: 迪杰斯特拉算法:求单源最短路的算法,要求图中不能有负边,否则就破坏了这个算法的贪心策略。 SPFA:也是求单源最短路的算法,这个算法在图中有负边的时候可以用,一般如果图中没有负边不用,毕竟是将图中所有点都
展开全文
WUT_23_邓皓文
发表于 2024-08-23 20:19:18
分层图最短路 链接:https://ac.nowcoder.com/acm/problem/236176 来源:牛客网 做法:直接去连边的话因为数据范围过大,所以会出现tle的现象,也有段错误的现象不知道是为什么,所以对于层与层之间的边,我们建立一个平台,同层的点到这个平台的距离为0,层与层之间的距
展开全文
查看本题
查看本题讨论
相关比赛
32312-算法基础精选题单补充题目
进入比赛
59977-【200题】算法基础精选题单
进入比赛
74488-ABTU校队赛Round5
进入比赛
83717-文达创意编程大赛
进入比赛
85967-Day06图论
进入比赛
等你来战
查看全部
牛客小白月赛101
报名截止时间:2024-09-20 21:00
牛客周赛 Round 61
报名截止时间:2024-09-22 21:00
牛客练习赛129
报名截止时间:2024-09-27 21:30
香港城市大学(东莞)2024新生排位赛
报名截止时间:2024-09-28 17:00
2024牛客国庆集训派对day1
报名截止时间:2024-10-01 17:00
2024牛客国庆集训派对day2
报名截止时间:2024-10-02 17:00
2024牛客OI赛前集训营-提高组(第一场)
报名截止时间:2024-10-05 22:00
2024牛客OI赛前集训营-普及组(第一场)
报名截止时间:2024-10-05 22:00
牛客2024年1024程序员节娱乐赛
报名截止时间:2024-10-24 21:00
扫描二维码,关注牛客
意见反馈
下载牛客APP,随时随地刷题