2018.10.30 NOIP模拟 有环无向图（dijkstra+巧妙建图）

传送门

建图巧妙啊。

对于每个点的出边，我们将它们排序之后依次连边。

这样可以把O(m2)O(m^2)O(m2)的边数变成O(m)O(m)O(m)的了。

连的权值就是max(edgemax(edgemax(edge_delta,0)delta,0)delta,0)

然后用边代替点跑dijkstradijkstradijkstra就行了。

代码