hust2015暑假集训 0713 A a dangerous trip

http://acm.hust.edu.cn/vjudge/contest/view.action?cid=82557#problem/A

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思想的算法.....

http://www.cnblogs.com/chensunrise/p/3721427.html

然而dp渣.....