首页 > ACM题库 > HDU-杭电 > hdu 2591 Distance待解决[解题报告]C++
2014
02-10

hdu 2591 Distance待解决[解题报告]C++

Distance

问题描述 :

A city contains a number of streets connecting several junctions. All the streets are straight line segments connecting two junctions. The walking distance between two points (each either a junction or some intermediate point of a street) in the city is the shortest path from the first point to the second. You are allowed to walk only along the streets. Streets never intersect outside the junctions. Now, your goal is to find the maximal walking distance among any two points in the city.

输入:

The input file contains several test cases. Each test case begins with two integers n and m ( 1<=n<=50, 0<=m<=n*(n-1)/2 ), which are the number of junctions and the number of streets. The following m lines each contain 3 integers Xi, Yi and Si ( 0<=Xi,Yi<n, 0<Si<=1000) indicating there is a street connecting junction Xi to Yi and the length is Si.

输出:

The input file contains several test cases. Each test case begins with two integers n and m ( 1<=n<=50, 0<=m<=n*(n-1)/2 ), which are the number of junctions and the number of streets. The following m lines each contain 3 integers Xi, Yi and Si ( 0<=Xi,Yi<n, 0<Si<=1000) indicating there is a street connecting junction Xi to Yi and the length is Si.

样例输入:

1 0
2 0
2 1
1 0 100
4 3
0 1 1
0 2 2
0 3 3
4 4
0 1 2
1 2 3
2 3 4
3 0 8

样例输出:

0.0
-1
100.0
5.0
8.5