| ||||||||||
Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
数据不够强,很多特殊情况都没有相应数据判断游戏是否win,需要分N种可能情况: 第一种情况,对room1做SPFA,如果没有负环,并且room1到roomN有距离,那么win。这是大多数人能考虑到的 第二种情况,如果存在一个负环,并且从这个环能够到达点N,那么也win。相应的如果从这个负环不能到达点N,则lost。这种情况很多人没有考虑到,所以WA了。 第三种情况,有多个负环,有的负环能到达点N,有的负环不能达到点N,也可以win。但是POJ的数据好像只包含了存在一个负环的情况,所以有的错误代码也能AC。 第四种情况,所有负环均不能到达roomN,但是能从room1到roomN, 不过由于在做最短路时判断出有负环就退出函数了, 这种情况没考虑,代码能也AC Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator