MNYC '17: Skiing Competition

View as PDF

Submit solution

All submissions

Best submissions

Points: 15 (partial)

Time limit: 1.0s

Memory limit: 256M

Authors:

Daniel123, aurpine

Problem type

A skiing competition is taking place. There are $N$ $N$ points on the hill and $M$ $M$ trails to get from one to another. It takes $t_m$ $t_{m}$ seconds to get from point $a_m$ $a_{m}$ to $b_m$ $b_{m}$ (and back) on the $m^\text{th}$ $m^{th}$ trail. It takes the same amount of time to get back on the same trail. The competition starts from $A$ $A$ and goes to $B$ $B$ . There are $Q$ $Q$ competitors racing. Due to rigging of the race, the $q^\text{th}$ $q^{th}$ competitor will take the ${k_q}^\text{th}$ ${k_{q}}^{th}$ fastest path. Two paths are identical in rank if they take the same amount of time. A competitor may not go back to a previously visited point.

To prepare the competitors, you will provide each of them with two pieces of information, the time they will take to finish the race, and the minimum time they will spend on one trail.

Constraints

For all subtasks:

$1 \le A, B \le N$ $1 \leq A, B \leq N$ , $A \ne B$ $A \neq B$

$0 \le t_m \le 10^6$ $0 \leq t_{m} \leq 10^{6}$

Subtask 1 [20%]

$2 \le N \le 100$ $2 \leq N \leq 100$

$Q = k_0 = 1$ $Q = k_{0} = 1$

$0 \le M \le \frac{N(N-1)}{2}$ $0 \leq M \leq \frac{N (N - 1)}{2}$

Subtask 2 [20%]

$2 \le N \le 100$ $2 \leq N \leq 100$

$1 \le Q, k_q \le 10$ $1 \leq Q, k_{q} \leq 10$

$0 \le M \le \frac{N(N-1)}{2}$ $0 \leq M \leq \frac{N (N - 1)}{2}$

Subtask 3 [20%]

$2 \le N \le 1000$ $2 \leq N \leq 1000$

$Q = k_0 = 1$ $Q = k_{0} = 1$

$0 \le M \le N \log N$ $0 \leq M \leq N \log N$

Subtask 4 [40%]

$2 \le N \le 1000$ $2 \leq N \leq 1000$

$1 \le Q, k_q \le 50$ $1 \leq Q, k_{q} \leq 50$

$0 \le M \le N \log N$ $0 \leq M \leq N \log N$

Input Specification

The first line will contain, $N$ $N$ $M$ $M$ $A$ $A$ $B$ $B$ $Q$ $Q$ , all space separated.

The next $M$ $M$ lines will contain three integers, $a_m$ $a_{m}$ $b_m$ $b_{m}$ and $t_m$ $t_{m}$ meaning a trail from $a_m$ $a_{m}$ to $b_m$ $b_{m}$ (and vice versa) will take $t_m$ $t_{m}$ units of time to ski.

The next $Q$ $Q$ lines will contain a single integer, $k_q$ $k_{q}$ , the designated path that the $q^\text{th}$ $q^{th}$ competitor will take.

Output Specification

$Q$ $Q$ lines containing two integers, the time it will take this competitor to finish the race, and the fastest time this competitor can take to get from one point to another. If there are no more paths, output -1 for that query.

Sample Input

Copy

Sample Output

Copy

Explanation for Sample Output

The trails look like the following:

$\text{[math]}$

The fastest path is $1 \to 2 \to 4 \to 5$ $1 \to 2 \to 4 \to 5$ .

The second fastest path is $1 \to 3 \to 4 \to 5$ $1 \to 3 \to 4 \to 5$ .

The third fastest (slowest) path is $1 \to 3 \to 2 \to 4 \to 5$ $1 \to 3 \to 2 \to 4 \to 5$ .

A fourth path doesn't exist.

The fastest trail on all these paths is $1$ $1$ unit of time.

Comments

0

imaxblue commented on Jan. 7, 2017, 10:07 p.m.

it says paths are identical in rank if they are equal. however, do they count as multiple paths still? example: If there were paths of length 4, 6, 6 and 8, would the ranks be 1, 2, 2 and 3 or 1, 2, 2 and 4. Also, if the minimum-path is different for two paths of the same length, what do we output?

0

aurpine commented on Jan. 7, 2017, 10:26 p.m.

It's 1, 2, 2, 3. Take the path that minimizes the minimum trail.