[传递闭包+SPFA最长路判正环]poj 1932:XYZZY
大致题意:
? ? 给出一个由n个房子,由若干的单向路连接起来,每个房子都有一个权值,意味着进入这个房子得到或者消耗的能量。把你放在1点,给你100点的初始能量。现在问你能否到达n点且到达时权值大于0.
?
大致思路:
? ? 很好的题目,参考了小媛神的思路 Orz。首先用spfa求最长路,同时判定是否存在正圈,再用floyd求出传递闭包。如果spfa求出的dis[1,n]大于0。或者从起点可以到达某个正圈,且这个正圈可以到达终点,则认为存在可行方案。
?
?