ZJU/ZOJ 1935 XYZZY 解题报告

题目大意是从点1出发，初始有100分，达到每个房间会减少或增加一定分数，问能否以正分到达点n（中间过程也必须是正分）。每个房间可经过多次。

先判断n到1的联通性，如果无法联通自然直接判不可到达。然后在与n联通的房间中从1开始找最长路，但由于一个房间可以经过多次，所以可能存在正权圈，而如果存在正权圈则到达n时必定可保证为正分。故可用Bellman-Ford或SPFA来找正权圈，如果存在正权圈（Bellman-Ford更新了n次仍无法结束、SPFA单个点入队次数大于等于n）或在更新过程中n的最长距离大于0则可判定可达，否则判定不可达。

3009544 2008-07-27 22:21:28 Accepted 1935 FPC 00:00.01 428K IwfWcf