dijkstra (練習筆記)

dijkstra (學習筆記)

思考方向

1. 最短路上除了w權值，還有其它，如k免費次數，考慮分層圖

經典題目解題

飛行路線

看到了最小值，考慮最短路，n=1e4，使用堆優化
k次免費，建立分層圖，去對使用與不使用兩種情況判斷跳圖

跳樓機

首先去寫式子，發現每個合法答案h為ax+by+cz=h，之后可以將by+cz看為k，使用k去分別加ax都是合法答案，所以去建立每個k下的最小值by+cz，使用同余最短路

同余最短路詳細講解ψ(｀?′)ψ