Dijkstra

hdu3873题目链接 题意：n个点的图。。。每个点可能被若干其他点保护。。。被保护的意思是。。。如果想访问某个点。。那么必须先访问保护该点的所有点。。。问从点1到点n的最小代价。。 思路：。。一开始写了spfa。。。然后一脸懵逼。。。因为我第一次访问某个点的时候无法保证距离是最短的。。。所以还是上dij吧。。。

题意是说，给定一个有向图，对于每一条边，问是否是 s 到 t 的最短路上一定会经过的边。 如果是就输出 yes。 如果不是，问能否通过减少这条边的权值（减少的权值就是修理费用），使得这条边成为新的最短路上的边。