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

POJ 3635 Full Tank?

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

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

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

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

代码不贴了。。

 

发表评论

电子邮件地址不会被公开。