POJ 3635 Full Tank? (bfs+优先队列)

于 2011年08月13日 发布在 算法&&ACM 跳到评论

POJ 3635 Full Tank?

我有种DP的感觉,也有种最短路的感觉,然后我就无语了。。

每个加油的地方要分拆成(c+1)个点,然后求最短路,但是我实在是太土了,真的是把点弄成了N(C+1)个,还建图了好多次,TLE到无语。。

后来看了题解,各种不明白,因为对所给图形的理解不是很好,这个题硬是搞了一天。

以前做过几个bfs优先队列的,但是对他的理解不是很深刻,现在慢慢了解,他跟dijkstra非常神似,也是一个贪心的过程,每次弹出最小量,然后他对应的那个值就确定了,因为他之后的不可能被更改。赶紧去找几个类似题目练练手~~~

代码不贴了。。

 

留下评论!

:wink: :twisted: :roll: :oops: :mrgreen: :lol: :idea: :evil: :cry: :arrow: :?: :-| :-x :-o :-P :-D :-? :) :( :!: 8-O 8)