UTS Open '15 #5 - Distribution Channel - DMOJ: Modern Online Judge

UTS Open '15 #5 - Distribution Channel

Points: 20 (partial)

Time limit: 3.0s

Memory limit: 256M

Author:

jeffreyxiao

Problem types

$\text{[math]}$

Distribution channels are often very confusing.

After acquiring enough funding and finally finishing the development for her product, Mrs. Evans wants to release it to the local market. However, the Canadian Competition Act prevents her from choosing the cheapest way to connect her stores.

In order to spend the least amount of money and abide by the Canadian Competition Act, she must find the second cheapest way to connect her stores.

Mrs. Evans hopes to open $N$ $N$ $(1 \le N \le 50\,000)$ $(1 \leq N \leq 50 000)$ stores and there are $M$ $M$ $(1 \le M \le 100\,000)$ $(1 \leq M \leq 100 000)$ possible connections between her stores. The $i^\text{th}$ $i^{th}$ connection connects station $a_i$ $a_{i}$ to station $b_i$ $b_{i}$ with a cost of $c_i$ $c_{i}$ . She can only choose $N-1$ $N - 1$ connections.

If it is impossible for her to do this, output -1.

N.B. The time limit is rather strict for certain slow languages like Python and Java. C++ is recommended for this question.

Partial Marks

For 25% of the marks, you may assume that $N \le 5\,000$ $N \leq 5 000$ , $M \le 10\,000$ $M \leq 10 000$ .

For 50% of the marks, you may assume that $N \le 10\,000$ $N \leq 10 000$ , $M \le 50\,000$ $M \leq 50 000$ .

Input Specification

The first line will contain $N$ $N$ , and $M$ $M$ . The $i^\text{th}$ $i^{th}$ of the next $M$ $M$ lines will contain $a_i$ $a_{i}$ , $b_i$ $b_{i}$ , and $c_i$ $c_{i}$ , where $(1 \le a_i,b_i \le N, a_i \ne b_i, 1 \le c_i \le 10\,000)$ $(1 \leq a_{i}, b_{i} \leq N, a_{i} \neq b_{i}, 1 \leq c_{i} \leq 10 000)$ .

Output Specification

A single line containing the second cheapest way to connect her stores.

Sample Input 1

Copy

Sample Output 1

Copy

Explanation for Sample Output 1

$\text{[math]}$

Mrs. Evans chooses the following connections for a total cost of $4$ $4$ :

$1 \to 2$ $1 \to 2$ with cost $1$ $1$
$1 \to 3$ $1 \to 3$ with cost $3$ $3$

Sample Input 2

Copy

Sample Output 2

Copy

Explanation for Sample Output 2

$\text{[math]}$

Mrs. Evans chooses the following connections for a total cost of $11$ $11$ :

$1 \to 3$ $1 \to 3$ with cost $2$ $2$
$3 \to 5$ $3 \to 5$ with cost $2$ $2$
$3 \to 4$ $3 \to 4$ with cost $3$ $3$
$2 \to 5$ $2 \to 5$ with cost $4$ $4$

Comments

1

bobhob314 commented on Feb. 11, 2015, 9:47 p.m.

When you say if it is possible, I think you mean the opposite.

-1

bobhob314 commented on Feb. 11, 2015, 9:48 p.m.

Relevant: In re Sample Input 2, CAN IT BE?