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

Re:这道题很多AC的程序其实都是错的!看看这两组数据

Posted by 2008022118 at 2010-05-28 15:26:29 on Problem 3169
In Reply To:这道题很多AC的程序其实都是错的!看看这两组数据 Posted by:Vidic15 at 2009-11-17 13:51:52
> 3 2 1
> 1 2 5
> 1 3 10
> 2 3 20
> 这个数据应该输出 -1
> 4 2 1
> 1 3 10
> 2 4 10
> 2 4 2
> 这个数据应该输出 -2
================================
楼主,你的答案才是错的吧!第二组应该是20的,根据题目意思手推都可得到。
估计楼主忘记了一个约束条件,牛是按编号大小排列的。如果就no.1来说,那么dist[i]-dist[i-1] >= 0; 所以结点i和结点i-1也应该建一条边。也就是你的数据中,2和3是有联系的。
第二组数据中,1和4号的最远距离20,当2和3号重合时最优!

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