题目大意输出一张有向带权图前k短路的长度思路分析这是道k短路板子题我们可以用Astar算法来实现它OIwiki相关算法的网页简单来讲，Astar定义了一个估值函数f(x)=g(x)+h(x)g(x)表示由起点到达x点的路程（不一定是最短路），而h(x)则是终点到x点的最短路程这个估值函数可以预估从该

P2901[USACO08MAR]CowJoggingG拓扑序+归并排序容易看出图是有向无环图，考虑在拓扑序上维护每个点的\(k\)短路。假如遍历到\(u\)，有边\((u,v,w)\)，\(u\)，\(v\)各自有自己的\(k\)短路，我们需要将\(u\)上的\(k\)短路加\(w\)后与\(v\)上排序，然后去前\(k\)小。直接做