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

@admin: Problem statement

rajneesh2k10 @ 1 Jun 2011 04:05 PM
@admin: Problem statement says: "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." As the graph is simple, so there is no parallel edge between any two pair of vertices. Hence every edge will have only one score. So why does the second statement says "minimum of the scores of its edges"? Please provide an explanation of the output also.

@admin: Ignore my above

rajneesh2k10 @ 1 Jun 2011 07:25 PM
@admin: Ignore my above comment. :)

Can anybody tell me the

k4rt33k @ 1 Jun 2011 10:17 PM
Can anybody tell me the complexity of the algorithm used? I want to eliminate the delay due to I/O in my solution. Thanks.

what is significance of line

manoharsingh23 @ 1 Jun 2011 10:19 PM
what is significance of line "best path as a path with the maximal score" here??Can anybody tell.

shouldn't the answer for

manoharsingh23 @ 2 Jun 2011 11:51 AM
shouldn't the answer for given case be: 0 1 3 1 0 2 3 2 0

i mean 0 1 3 1 0 2 3 2 0

manoharsingh23 @ 2 Jun 2011 11:52 AM
i mean 0 1 3 1 0 2 3 2 0

@writer Is the time limit

calc_saransh @ 2 Jun 2011 11:59 AM
@writer Is the time limit fine for java.. (2x times but still) my code produces the matrix in case of 1000*1000 in nearly 1.8s but times out due to printing 10^6 numbers.. And there is only one java AC submission... Please comment... thanks

How can the score for path

vikram535 @ 2 Jun 2011 01:43 PM
How can the score for path between 0 and 1 can be 2? Shouldn't it be 1? Please explain the output if 2 is correct.

@vikram535: There is a path

kashyap_kumar @ 2 Jun 2011 02:00 PM
@vikram535: There is a path 0-->2-->1. This path has a minimum score of 2.

can anyone please explain me

ishank006 @ 2 Jun 2011 05:53 PM
can anyone please explain me the output...

Thanks for the explanation

vikram535 @ 2 Jun 2011 08:56 PM
Thanks for the explanation Kashyap...

Shouldn't the time limit in

warawara @ 3 Jun 2011 08:42 PM
Shouldn't the time limit in the problem description be 30s?

please point me the technique

aseem_pandey @ 4 Jun 2011 03:45 AM
please point me the technique for faster IO. I hope this will not violate the contest rules :).

@assem_pandey: check out some

dabbcomputers @ 5 Jun 2011 12:45 PM
@assem_pandey: check out some public code frum older contest. many coder used fast IO in many problems.

my algorithm is taking time

uditiiita @ 6 Jun 2011 12:58 PM
my algorithm is taking time of the order of O(ve) but i am still getting tle.... and i am also using faster input / output methods. please someone help should i optimize my algo further or io optimization is required?

this is a request to the

calc_saransh @ 6 Jun 2011 01:56 PM
this is a request to the writer that please set time limit considering slow languages, the same java code of mine got AC when coded in C++... thanks..

calc_saransh: The time limit

rahulakaneo @ 6 Jun 2011 07:13 PM
calc_saransh: The time limit had to be set strictly to not allow weaker solutions to pass the system tests. I'll try to take care of slower languages the next time. Regards, Rahul

do we need to consider the

codeprav @ 7 Jun 2011 09:25 PM
do we need to consider the cycle that comes in the path from u to v that is from initial to final

@admin:do we need to consider

codeprav @ 7 Jun 2011 09:26 PM
@admin:do we need to consider the cycle that comes in the path from u to v that is from initial to final

There seems to be something

subhrakb @ 8 Jun 2011 03:37 AM
There seems to be something wrong with the timing system for this problem. I have created a 1000 X 1000 input for a fully connected array (i.e. 499500) edges and weights for each of the order 10^8 and my Java program runs in about 4 seconds on this input. This is the maximum input possible for this problem per specs. The time limit for Java is 3 X 2 = 6 seconds so I am well under limit. However, when I upload I am getting TLE consistently. Can someone please check? Are you testing with higher limits than stated in the program? Thanks.

pls help me , path is defined

codeprav @ 8 Jun 2011 09:54 AM
pls help me , path is defined here in what sense

@sukhrab: No constraint has

rahulakaneo @ 8 Jun 2011 02:06 PM
@sukhrab: No constraint has been violated in generating the input sets. @codeprav: http://en.wikipedia.org/wiki/Path_(graph_theory)

@rahulakaneo: I was talking

subhrakb @ 8 Jun 2011 06:37 PM
@rahulakaneo: I was talking of timing while checking the submission, not contraint violation. My program is able to compute a fully connected 1000 x 1000 graph in 4 s on my system but getting TLe after submission. Since it is in Java, the limit should be 6 s so mine is well under that. So what's wrong?

@subhrakb: I have seen some

rahulakaneo @ 8 Jun 2011 09:42 PM
@subhrakb: I have seen some of your submissions. You've used a wrong algorithm. Your program should produce the desired output on Judge (in time limit). The judge's system might not be as fast as your system.

@rahulakaneo :: r u admin for

mkagenius @ 9 Jun 2011 01:24 AM
@rahulakaneo :: r u admin for this problem ?

I am a bit confused about the

prashantc29 @ 9 Jun 2011 02:33 AM
I am a bit confused about the time limit thing. In the problem it is mentioned that time limit is 3s. But all the successful submissions have taken more than 3s. There are submissions with time 20 s and more also. So what is the exact time limit needed. Because I am constantly getting TLE.

Time limit is 3s per input

rahulakaneo @ 9 Jun 2011 04:25 PM
Time limit is 3s per input data set. There are 10 data sets in total.

How many FloPS has your

genyaz @ 10 Jun 2011 02:36 PM
How many FloPS has your server? I had sent checker test, and it showed that it is about 5*10^6 sqrt operations per sec. Is it true?

After 4 submissions still

bagrawal @ 11 Jun 2011 02:26 AM
After 4 submissions still getting TLe, how do I get it right now.

SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:

CodeChef is a global programming communityCodeChef hosts online programming competitions