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渣…..

 

作者: CrazyKK

ex-ACMer@hust,stackoverflow-engineer@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz