Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

数据不够强,很多特殊情况都没有相应数据

Posted by xiaojiegt at 2011-08-12 10:04:43 on Problem 1932
判断游戏是否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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator