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:用求最短路的O(n^3)的算法改改就可以了。

Posted by Ontheline at 2009-05-21 21:05:17 on Problem 2253
In Reply To:用求最短路的O(n^3)的算法改改就可以了。 Posted by:gzw_02 at 2008-11-23 12:32:28 
呵呵，遍历中间节点后，if( p[i][j] > max(p[i][k],p[k][j]) ) 那么肯定能降低每步的距离了，这个题是个完全图，不用考虑图的连通性。那么就加入节点k,p[i][j]=max(p[i][k],p[k][j]).呵呵，Floyd真是个好东西。
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