Maximal Score Path

Problem code: RG_01

All submissions for this problem are available.

Problem Statement

Given a weighted and undirected graph G = (V, E), let us define the score of an edge as its weight, and the score of a path as the minimum of the scores of its edges. For each pair of vertices (u, v), let us define a best path as a path with the maximal score, that starts at u and ends at v. Your task is to find out the score of a best path over all pairs of distinct vertices (u, v) given the description of the graph G.

Input

The first line contains V, the number of vertices, and E, the number of edges in the graph. The graph will be weighted, undirected, simple (no self loops and no parallel edges), and connected. Each of the next E lines contains three non-negative integers u, v, and w, denoting that there is an edge (u, v) in the graph with a score of w. u and v are guaranteed to be distinct, and no edge will repeat in the input.

Output

Output a total of V lines each containing V integers. The vth integer on the uth line should be 0 if u = v, or the score of a best path that starts at vertex u and ends at vertex v.

Constraints

2 ? V ? 1000
V - 1 ? E ? V(V - 1)/2
0 ? u, v ? V - 1
0 ? w ? 10^8

Example

Input:
3 3
0 1 1
1 2 2
0 2 3

Output:
0 2 3
2 0 2
3 2 0


 Warning
 Large Input/Output. Use faster Input/Output techniques.

Author: rahulakaneo
Date Added: 10-04-2011
Time Limit: 3 sec
Source Limit: 50000 Bytes
Languages: ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, ERL, F#, FORT, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC


Comments

can anyone explain the answer

atul agrawal @ 14 Jan 2012 10:51 PM
can anyone explain the answer for the test case

can we have for this problem

nitish712 @ 3 Mar 2012 04:54 PM
can we have for this problem a path which goes through the same vertex twice?? if yes then all the elements of the matrix should be having the largest score itself....

atul agrawal First draw the

fedorpetrov2 @ 11 Apr 2012 09:48 AM
atul agrawal First draw the graph on paper then look Between vertices 0 and 1 we have two paths: 0 - 1 and 0 - 2 -1 The SCORE of path 0 - 1 is 1 - that's simple enough. And the SCORE of path 0 - 2 -1 is 2. The SCORE of path 0 - 2 -1 is 2 because it has two edges: 0 - 2 with SCORE 3 and 2 - 1 with SCORE 2. 2 is less than 3 so The SCORE of path 0 - 2 -1 is 2. So we select BEST PATH 0 - 2 -1 with SCORE 2 since it's SCORE is bigger than SCORE of path 0-1 which is 1. I hope i explained clear enough.

what the fuck is wrong with

fedorpetrov2 @ 11 Apr 2012 09:50 AM
what the fuck is wrong with line breaks?!

SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:

HELP

Program should read from standard input and write to standard output. After you submit a solution you can see your results by clicking on the [My Submissions] tab on the problem page. Below are the possible results:

 

  • Accepted Your program ran successfully and gave a correct answer. If there is a score for the problem, this will be displayed in parenthesis next to the checkmark.
  • Time Limit Exceeded Your program was compiled successfully, but it didn't stop before time limit. Try optimizing your approach.
  • Wrong Answer Your program compiled and ran succesfully but the output did not match the expected output.
  • Runtime Error Your code compiled and ran but encountered an error. The most common reasons are using too much memory or dividing by zero. For the specific error codes see the help section.
  • Compilation Error Your code was unable to compile. When you see this icon, click on it for more information.

    • If you are still having problems, see a sample solution here.

CodeChef is a global programming communityCodeChef hosts online programming competitions