这个题倒是不难，但是我当时对于题目的理解导致写出来很复杂，所以记一下踩的坑。其实就是最短路树的应用，我的想法是先删掉不在树上的边，然后对于树上的边先删除连叶子的边，以此类推。这样写倒是没有错也可以过。
但是！这个题题面里说的是最多k个，所以其实根本不用考虑去掉非树边什么的，假如k>n-1的话只输出n-1条树边也是对的！这就省了好多代码了。其次，根本不用使用拓扑排序那样的处理过程（就是先去掉叶子这种），因为想一下dijkstra的过程就可以发现，每次从优先队列中取出来一个节点后，这个节点的前驱最短路其实已经确定了，只要在这时候把其前驱记录下来，根据dijkstra的每一步往外扩展一步的操作，按照这个顺序搞下去最后的记录表中的顺序其实就是拓扑序。。。。依次输出即可。 继续阅读“[CF][图论][最短路树] codeforces 1076D Edge Deletion”
题目链接 https://cn.vjudge.net/problem/UVALive-4080
最短路基础题，有意思的部分在于最短路树这个东西的应用，还有对复杂度的正确估算（莽
看题目意思，基本上能确定枚举那条要去除的边然后算每种情况的c，但是如果直接这样的话复杂度会是n*m²*logn,就题目数据量而言基本上不可能过的。所以就要找其他方法来降低复杂度，考虑到，去掉一条边也许不会对以某些点为原点的到每个点的单源最短路产生影响（也就是不在这些点的最短路树上的边），可以试着预处理出来初始状态下每个边的影响到的点的集合，在枚举到这条边的时候只需要重新计算这些点的最短路而不用每次都计算所有点的最短路，这样的话可以把复杂度降低到n²mlogn。不得不吐槽一下这个解法，说实话感觉并没有降低多少就卡过了时限，数据刻意友好么。。。。比赛的话就算能想到这个也不一定敢写吧emmm
坑点是有重边，果然做图论最重要的是搞清楚图的类型。。。重边啊自环啊什么的真的烦,还有一开始小根堆写成大根堆了，又是wa又是t的 继续阅读“[蓝书][图论][最短路][坑] UVALive 4080 Walfare And Logistics”
http://codeforces.com/contest/1064/problem/D
这个题最操蛋的是我把复杂度弄错了导致没有敢写暴力。。不过官方并没有出题解所以我也不知道我的做法是否可行，只能说通过了目前的所有数据。
做的思路就是求出来原点到每个点所用的最小的left和最小的right，求的方法就是暴力bfs，但是这里有个问题是有可能会有一个点可以通过多条路径到达，那么该如何确定最小值？如果直接裸搜不打标记会使得无限循环，如果打标记则会使得多种可能没有考虑，我这里用了一个玄学剪枝就是当当前点的下一个点的数据有被更新的时候才加到queue里，否则就不加，可以保证去掉了很多无用的扩展也可以保证搜索可以结束。另外一个优化是加了点是否已经在queue内的判断，可以避免多余的入队操作（这个貌似也可以用在一般的dij里啊）
