Christmas Party

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 2.0s
Java 3.5s
Python 3.5s
Memory limit: 128M
Java 256M
Python 256M

Problem type

Surge is hosting a Christmas party at his house and needs to stock up on juice!

Surge's town consists of N houses and M two-way roads connecting them. Surge lives in house 1. Each road i takes w_i minutes to walk across. He wants a person from every house in his neighbourhood to bring a bottle of juice to his house. What is the minimum total time that the citizens can spend walking from their house to Surge's house?


In all test cases, 1 \le w_i \le 2 \times 10^5 for all 1 \le i \le M

Subtask 1 [50%]

1 \le N \le 1000, 1 \le M \le 3000

Subtask 2 [50%]

1 \le N \le 10^5, 1 \le M \le 2 \times 10^5

Input Specification

First line: N (the number of houses) and M (the number of roads).

The next M lines each contain u_i, v_i, and w_i indicating a two-way road connecting houses u_i and v_i and takes w_i minutes to traverse (1 \le u_i, v_i \le N).

Output Specification

One integer: the minimum total time possible in minutes.

Sample Input 1

5 6
1 5 3
3 5 10
2 5 6
4 5 8
2 3 5
2 4 9

Output for Sample Case 1

Explanation for Sample Case 1

The town looks as such:

Town Graph Diagram

  • House 5 can go straight to house 1, taking 3 minutes.
  • House 3 can go to house 5 then house 1 taking 13 minutes.
  • House 2 can go to house 5 then house 1 taking 9 minutes.
  • House 4 can go to house 5 then house 1 taking 11 minutes.

The total time taken was 3+13+9+11=36 minutes.


There are no comments at the moment.