UVA 10246 Asterix and Obelix (最短路变形)

UVA 10246 Asterix and Obelix

乍看是带点权的最短路,实际上最短路再加上最大点权最小的时候才是最短,即min{ path(S,T) + min{w[i]|i on path from S to T}}.我表示没有思路,看的题解做的。。比如说我们要求出S,T的“最短路”,我们可以枚举最大中间节点,因为这条路必经经过一个最大中间节点,比如说我们找到点U的时候,就假设U是S到T路径上点权最大的点,可以把图上点权大于U的点去掉然后d[ S, U ] + d[ U, T ] + w[U]便是假设u点权最大时候的“最短路”,每给出一个询问,查询即可。

(更多…)

继续阅读 →