package
0.0.0-20241220224003-b7cf03a90b2b
Repository: https://github.com/szhou12/leetcode-go.git
Documentation: pkg.go.dev
# README
2093. Minimum Cost to Reach City With Discounts
Solution idea
Dijkstra
要点总结:
- 任意两个node之间有 "两条边"， 一条edge的weight = toll，另一条edge的weight = toll/2.
- Dijkstra算法在expand的时候, 要分别把两条边的情况都Push进去.
- Dijkstra算法的结果储存在 二维矩阵 = # nodes X # discounts used
- node储存双状态: node 储存 位置信息+已使用discounts次数信息
Time complexity = $O(E \log E)$ where $E = n * m$, $m = $ # of discounts