首页
Python
Java
前端
数据库
Linux
Chatgpt专题
开发者工具箱
449b专题
【Codeforces】449B Jzzhu and Cities 最短路
传送门:【Codeforces】449B Jzzhu and Cities 题目大意:一个n个节点的无向图,节点编号1~n(其中1为起点),其中有m条普通普通,还有k条从起点出发的特殊边,问最多去掉多少的特殊边使得从起点到其他所有点的最短路径的距离不变。 题目分析:这题的意图很明显啊,就是要我们去求最短路啊。那么怎么求会比较好呢?其实我们可以很容易的发现如果从起点通过边权为c的特殊
阅读更多...
Jzzhu and Cities CodeForces - 449B
点击打开链接 做的很迷的一道题。。 开始用Dijkstra 将公路铁路都加入图中 看每一个有铁路直达的点 能否通过除这条直达铁路之外的路径来松弛 即该点是否存在代价小于等于这条铁路的路径 WA的很离谱 一时还找不到问题的原因 留坑。。也希望路过的大佬指正。。 #更正 填坑 其实没想的那么难 先记录下每个点通过走铁路直达的最短距离(dis2) 同时记录下从首都
阅读更多...