P9534

好题。 首先考虑到对于任意的边的输入顺序，分层图是不会变的，即所有点到根的最短距离不变。 那么分为两种边，分别为不同层的边相连，相同层的边相连。 显然第二种边是无用的，我们将其放到最后输出即可。 由于下层的决策会影响上层的决策而且不同层之间的边的顺序不会影响答案，所以我们按分层图从大到小处理。 不妨 ......