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

这组数据的确是本题的BUG

Posted by haqishen at 2015-01-08 18:13:13 on Problem 3169
In Reply To:求解释这组数据 Posted by:testid1 at 2014-03-12 14:06:37
原则上来讲我也支持输出-1.。。
我用dijkstra算法的话,是在途中发现起点到某一点的最短距离为负数则输出-1.
算法结束后,如果起点到终点距离为INF,则输出-2.
根据dijkstra算法,如果没有一条线连接到起点,那就不会触发-1这个结果,而是直接输出-2.

其次用Bellmanford算法的话,是在更新起点到所有点距离V次(牛的总数)后,根据能否继续更新来判断是否输出-1。
但是从起点没有连线的话,就连1次更新都进行不了,所以自然输出不了-1了。。。


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