Welcome   HUNAN NORMAL UNIVERSITY ACM/ICPC Judge Online
Home
FAQs
Problem Set
Practices
Online Contests
Major Exercises
OI Special
Judgement
Submit
Online Status
User Ranklist
Users
Register new
Login
Web Links
Hunan Normal University
College of Information Science and Engineering
校园网络 
Time Limit: 1000ms, Special Time Limit:2500ms, Memory Limit:32768KB
Total submit users: 37, Accepted users: 34
Problem 10615 : No special judgement
Problem description
    校园里有N(1≤N≤500)台计算机,现在我们测得这些计算机两两之间的Ping时间,得到对称矩阵Pij(1≤i,j≤N)。现在,我们需要用若干直连线将这N台计算机连接起来,使得任意两台计算机之间可直接或间接地通信。我们认为,计算机A可以和自身通信,Ping时间规定为0;若AB之间有直连线且Ping时间为p,则BAPing时间也为p;若AB之间可以通信,BC之间可以通信,则AC之间可间接通信(A≠B≠C)
  对于每一种连接方案,记T=max{Pij|ij可直接通信}。请你编程计算所有连接方案中T的最小值。

Input
    输入数据的第一行为一个整数N(1≤N≤500),表示计算机数目;
  接下来是一个N×N的对称正整数矩阵,表示计算机两两之间的Ping时间,整数的范围不超过5000
  注意:数据量大,强烈建议使用scanf()读入,C++流输入会浪费大量时间。

Output
    输出数据只有一个整数,为T的最小值。

Sample Input
6
0 1009 2833 2387 3333 3917
1009 0 1349 2600 2950 2437
2833 1349 0 2763 4484 1555
2387 2600 2763 0 2675 3632
3333 2950 4484 2675 0 4607
3917 2437 1555 3632 4607 0
Sample Output
2675
Problem Source
  2010年河北大学程序设计竞赛

Submit   Discuss   Judge Status  Problems  Ranklist 

HUNAN NORMAL UNIVERSITY ACM/ICPC Judge Online, Version 2010.5.5.final.
Web visits:2293 today,16259020 total, since 2010-05-07