从dijkstra开始

开学不久补了一道题目，https://atcoder.jp/contests/abc319/tasks/abc319_f

基础性的步骤是用优先队列维护可以走到的点，弹出代价最小的点，实现一个动态的贪心过程。相当于我站在一棵树上的一点，可以移动到一些与这棵树相接的点，从而扩大树的范围，也扩大自己将来可以移动的范围。当时觉得这个priority_queue的使用虽然基础，但想不到.

印象里暑假里研究过dijkstra算法，做过几道题. 看到过多源bfs等等，但最后也没有留下什么印象。

上学期在atcoder上看到一道题，是dijkstra的板子改了改，题意是有k种不同面值的钞票，求能凑出第m小的面值。解法是建k条不同的边，从0面值开始搜索，放进优先队列，求第m个出队的面值。https://atcoder.jp/contests/abc297/tasks/abc297_e

我觉得这道题可以被重述成一道图论的题。那么重述前后不变的本质是什么呢？

事实上在这里priority_queue做到的也是储存所有可能取到的值，从中拿出最小的第k个。无非这里我们一边取一遍算。这个用法本质上很简单。

印象里当年百度之星初赛第二场也有一道可以被建模为图论的题。

然后，昨天补到一道题，这道题比较dijkstra了。https://codeforces.com/gym/104460/problem/K

题意是$n$点$m$边无向图，Baobao从点$1$出发，想走到k个点之中的一个，任何一个都可以，边权是所需的时间。但当他走到第$i$点时，有$d_{i}$条以$i$点为端点的边会堵住(哪$d_{i}$条都有可能，每次走到$i$点时，堵住的边也可能不一样)，问在最差情况下，Baobao走完的最小时间是多少？

如果从起点开始顺着走的话，不能确定哪几条边堵着最差；把k个终点的dis设为0，放进优先队列，然后倒推跑dijkstra,这时和之前的几道题情况一样，当点i弹出优先队列时，我们拿到一个点i到终点的最小距离。这时让从点i连在这条路径的边被堵住，即，每次Baobao走到点i,这条边总是堵的。否则只要这条边不堵，就可以最快的到达某个终点。

所以此时的点i也不能再转移出别的点了。当点i第二次被弹出时，找到了到它的第二短路径，以此类推。那么，当第$d_{i}+1$次弹出i点时，找到的就是最坏情况下，点i到终点的最短路。