📌 📄 内容摘要:
@ninijia 在 Leetcode每日一题练习 ------ 2699. 修改图中的边权 中发帖
从Leetcode 每日一题练习继续讨论：
2699. 修改图中的边权
2699. Modify Graph Edge Weights
题解
本题首先注意到目标是要求最短路, 而本题中边权重除了-1外均为正值, 而负值也只有-1一个. 则可以先忽略所有边权重为-1的边, 对其他边可以使用dijistra算法(使用优先级队列优化算法效率). 得到的结果有四种情况, 比target大, 比target小, 和target相等, 以及从源点到目标点之间没有可行路径. 若和target相等, 则将其余-1边均置为一个任意大的数, 不影响最终结果即可. 考虑到target最大为10^9, 可以置为10^9+1. 若比target小, 则不可能通过修改-1边的值得到一条最短路径和target相等(因为当前最短路径已经比target小, 若得到新的最短路只能比当前最短路更小, 只会距离target...
────────── 链接信息 ──────────
🔗 论坛链接: linux.do
📎 访问地址: https://linux.do/t/topic/189305/1
─────────────────────────────
📢 来源：LINUX DO
