📌 📄 内容摘要:
@SomeBottle 在 Leetcode每日一题 —— 3650. 边反转的最小路径总成本 中发帖
思路
很快能反应过来这就是在找最短路，但是反转边这个玩意看上去有些唬人的。
不过仔细想想可以发现，求解的最短路中，我立足于某个节点 u 时，只需要决定下一步走向哪一个相邻节点 v，也就是对于每个结点至多只会有一条出边，如果没有合适的出边，那么就需要反转一条入边作为出边，也就是路径上某个节点至多也只会有一条入边反转，不用担心一个节点有多个入边的情况。
基于这个思路，其实可以直接让相邻节点的边都反转一份加入表中（代价 \times 2 ），然后用 Dijkstra 这类最短路求解算法求解即可。
说回来好久没写 Dijkstra 了，不过这个最短路求解的思路真的挺自然的，也算是复习了一下。 (´▽｀)
代码
堆优化的 Dijkstra
struct Node{
int idx; // 节点下标
int cost; // 从起点到当前点的代价
// 子 > ...
────────── 链接信息 ──────────
🔗 论坛链接: linux.do
📎 访问地址: https://linux.do/t/topic/1519881/1
─────────────────────────────
📢 来源：LINUX DO
