DMOPC '16 Contest 4 P5 - Migrant Mascot - Olympiads Online Judge

DMOPC '16 Contest 4 P5 - Migrant Mascot

View as PDF

Submit solution

All submissions

Best submissions

Points: 10 (partial)

Time limit: 1.0s

Memory limit: 64M

Author:

Phoenix1369

Problem type

After indulging in one of her guilty pleasures for some time, Molly tears herself away from the booth. She begins moving along with the large crowds of the carnival and hopes this will lead to one of the fabled carnival attractions. After some time, Molly notices a busy intersection in front of her. There were no traces of the carnival to be seen…

The city in which Molly lives consists of $M$ ~M~ undirected (relevant) roads and $N$ ~N~ tourist ~~traps~~ attractions numbered from $1$ ~1~ to $N$ ~N~, with $1$ ~1~ being the carnival.

Molly exhibits a preference for certain types of roads over others and thus assigned each road with a preference value $p_i$ ~p_i~. The higher this value is, the better the road will be for Molly to traverse. With many paths leading away from the carnival to choose from, Molly will only remember a path by the lowest preference value of the roads which comprise it.

Molly would like to know the best possible value of any path leading from the carnival to a specific tourist attraction.

Since Molly cannot decide which of the tourist attractions in her city to visit next, she has enlisted your help.

Write a program to determine the desired value for each of the tourist attractions to help Molly!

Note: A path is a series of roads joining any two (different) attractions.

Input Specification

Line $1$ ~1~: Two space separated integers $N$ ~N~ and $M$ ~M~, denoting the number of tourist attractions and relevant roads respectively.
Line $2 \dots M+1$ ~2 \dots M+1~: Three space separated integers $a_i, b_i, p_i$ ~a_i, b_i, p_i~, denoting an edge between tourist attractions $a_i$ ~a_i~ and $b_i$ ~b_i~ $(1 \le i \le M)$ ~(1 \le i \le M)~ with a weight of $p_i$ ~p_i~.

Output Specification

Your program should output $N$ ~N~ lines, the $i^{th}$ ~i^{th}~ of which represents the best possible value of the $i^{th}$ ~i^{th}~ path leading from the carnival to the $i^{th}$ ~i^{th}~ attraction.

Constraints

For all subtasks:

$a_i \ne b_i$ ~a_i \ne b_i~

$1 \le a_i, b_i \le N$ ~1 \le a_i, b_i \le N~

$1 \le p_i \le 10^9$ ~1 \le p_i \le 10^9~

$1 \le M \le \min\left(\frac{N(N-1)}{2}, 2 \cdot 10^5\right)$

It is possible to reach every attraction from every other attraction.

Subtask 1 [20%]

$2 \le N \le 15$ ~2 \le N \le 15~

Subtask 2 [30%]

$2 \le N \le 350$ ~2 \le N \le 350~

Subtask 3 [50%]

$2 \le N \le 2 \cdot 10^5$ ~2 \le N \le 2 \cdot 10^5~

Sample Input

Sample Output

0
3
7

Explanation

$\text{[math]}$

Because Molly was just at the Carnival, she is no longer interested in spending time there. As a result, the value for # $1$ ~1~ is (always) $0$ ~0~.

The lowest preference value of either path leading to attraction # $2$ ~2~ is $3$ ~3~.

There are two paths leading from the carnival (# $1$ ~1~) to attraction # $3$ ~3~: $1 \to 3$ ~1 \to 3~ and $1 \to 2 \to 3$ ~1 \to 2 \to 3~, with respective values (as Molly recalls) of $7$ ~7~ (the only preference value of the path) and $\min(1 \to 2, 2 \to 3) = \min(3, 3) = 3$ .

Comments

1

devnarula commented on June 27, 2020, 9:05 p.m.

What is the issue with my code? It works with CCC '03 S5 Trucking trouble but does not work with this question

-4

sushi commented on June 29, 2020, 2:59 p.m.

Your code is incorrect in some cases. You are simply checking if a weight of an edge is bigger than the previous answer stored in your distance array, however it does not reflect the intention of the problem, which defines the weight of a path is the minimum of all edges along that path, and you need to find such a maximum path, not just one edge.

3

devnarula commented on June 29, 2020, 3:54 p.m.

So, I fixed the issue of minimum now, by keeping a visited array and if a node is already visited I update it with min() of all roads within a path to prev node and maximum of that value, its initial distance. It was able to pass batch #2 but fails in batch #3

-13

sushi commented on June 29, 2020, 4:01 p.m. ← edit 3 →

Please do not clutter up the comment section, if you wish to receive more insight on solving the problem, please visit the dmoj discord and go to the #help channel.

This comment is hidden due to too much negative feedback. Show it anyway.

1

Xenosi commented on Oct. 20, 2019, 6:52 p.m. ← edited →

I'm not sure if I'm understanding the problem correctly but shouldn't the answer for the sample input be 0 3 3?

Edit: I realized that Molly goes to the path with the largest preference value. Thanks injust!

1

injust commented on Oct. 20, 2019, 7:39 p.m.

$7$ ~7~ is the maximum preference value of all paths from $1$ ~1~ to $3$ ~3~.

The preference value of a path is the lowest preference value of the roads that make up said path.

9

astrocat879 commented on May 26, 2019, 7:13 p.m. ← edited →

Raise memory limit for python?