package
0.0.0-20241220224003-b7cf03a90b2b
Repository: https://github.com/szhou12/leetcode-go.git
Documentation: pkg.go.dev
# README
2699. Modify Graph Edge Weights
Solution idea
Dijkstra
思路总结
- 题目要求所有权重为-1的边一定要修改成正数。所以，第一步先把所有负数边的权重改成最小正数1，跑一遍Dijkstra，看看最短路径的总消耗是否等于target。如果 > target，显然找不到任何可行解；只有 <= target才可能存在解。但是，当 < target时，同时还需要满足最短路径途经至少一条“修改”边，否则也不存在可行解。