hust2015暑假集训 0713 A a dangerous trip

Jul 13, 2015 · 1 min read

Zk的解法：拆点，把每一个点存成两份，r[i]和r[n+i]

连边的时候如果u和v相连，我们就分别连 u&&v; 和 u+n&&v;+n 和 u&&v;+n 其中最后一个存法是要使用魔法的情况...

最后求从1到n+n的最短路径即可

如图

斜着的边表示使用魔法的情况。

由1到n+n，只经过一次斜边，这是与题干中只使用一次魔法相对应的....

由于权值变成一半可能出现浮点数...

我们不妨先权值先整体*2

最后结果的时候再/2

zk好聪明（逃）

然后还有一种是鲍佳学长的dp思想的算法.....

然而dp渣.....