1. 首页
  2. 最短路

HDU 3499 Flight (分层图最短路)

题目链接:点我~~

题意:在N个点,M条带权边的图上,查询从点S到点E的最短路径,并且有一次机会可以把一条边的权值变成原来的二分之一。

思路:利用分层图的思想建图,
u->v需要建立,addedge(u+n,v+n),addedge(u,v+n,w/2),表示分两层,当从上层到下层,即使用了题中所给的条件。

 

评分 0, 满分 5 星
0
0
看完收藏一下,下次也能找得到
  • 版权声明:本文基于《知识共享署名-相同方式共享 3.0 中国大陆许可协议》发布,转载请遵循本协议
  • 文章链接:http://www.carlstedt.cn/archives/1145 (转载时请注明本文出处及文章链接)
上一篇:
:下一篇

发表评论

gravatar

快来吐槽一下吧!

  1. .01 4:06
  2. .02 1:47
  3. .03 3:39
  4. .04 1:40