c++ problem26:

Floyd-Warshall

Time Limit: 3 seconds

Problem Description

For a directed graph G=(V, E), edge e corresponds to a weight w, which can be regarded as the distance between two points on the edge. in

a connected graph, we can find a central point median, the sum of the distance from this point to other points is minimal.

Input File Format

There will be a positive integer T at the beginning, which means that there will be T input data.

The first line of each input has two positive integers n and m, representing n points and m edges on the graph, 2 ? n ? 1000,

1 ? m ?50000, each point numbered 0 ~ n-1.

The next m rows each have three positive integers u, v, and w, representing an edge from u to v with a weight of w, 0

Output Format

each line outputs the center point of the graph . If there are more than one center points, the point with the smallest number is output.

Example Sample Output Sample Input 1 4 6 0 11 02 1 03 1 122 231 132 Example Sample Output Sample Input 1 4 6 0 11 02 1 03 1 122 231 132