DMOPC '16 Contest 4 P5 - Migrant Mascot

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 2.0s
Memory limit: 64M

Author:
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 undirected (relevant) roads and N tourist traps attractions numbered from 1 to N, with 1 being the carnival.

Molly exhibits a preference to certain types of roads over others and thus assigned each road with a preference value 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: Two space separated integers N and M, denoting the number of tourist attractions and relevant roads respectively.
Line 2 \dots M+1: Three space separated integers a_i, b_i, p_i, denoting an edge between tourist attractions a_i and b_i (1 \le i \le M) with a weight of p_i.

Output Specification

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

Constraints

For all subtasks:

a_i \neq b_i

1 \le a_i, b_i \le N

1 \le p_i \le 10^9

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

Subtask Points N
1 20 1 < N \le 15
2 30 1 < N \le 350
3 50 1 < N \le 2 \cdot 10^5
  • It is possible to reach every attraction from every other attraction

Sample Input

3 3
1 2 3
2 3 3
1 3 7

Sample Output

0
3
7

Explanation

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

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

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


Comments


  • -4
    mindplaysgaming  commented on Aug. 28, 2019, 11:59 a.m.

    XD


    • 1
      Plasmatic  commented on Aug. 28, 2019, 12:30 p.m.

      Please don't post solution code in the comments. It disrupts other users who are trying to solve the problem


  • 6
    astrocat879  commented on May 26, 2019, 3:13 p.m. edited

    Raise memory limit for python?


  • 1
    aeternalis1  commented on Aug. 10, 2017, 10:25 a.m. edit 2

    WA in batch 3?

    I implemented my solution for CCC '03 S5 Trucking Troubles, which AC'd there, but I get WA in test case 1 of batch 3. Is this due to some sort of edge case? EDIT: Resolved


  • 0
    septence123  commented on Feb. 17, 2017, 10:40 a.m.

    Why am i getting MLE for the first test case it is using 171 mb? even though n is in between 1 and 15.


    • 0
      Kirito  commented on Feb. 17, 2017, 11:09 a.m.

      PyPy sacrifices memory for speed, and as such uses around 3 times as much memory as CPython.


      • 0
        septence123  commented on Feb. 17, 2017, 11:18 a.m.

        Submitted same code in python 2.7 uses more memory than in pypy, still MLE. :(


        • 5
          moladan123  commented on Feb. 21, 2017, 8:52 p.m.

          I ran into a similar problem when using python. Considering this problem was designed around being solvable in c++, the author must have not taken into account how slow python is. Who knows though, it might just be my complexity is too high.