MNYC '17: Skiing Competition

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 2.0s
Memory limit: 256M

Authors:
Problem type

A skiing competition is taking place. There are N points on the hill and M trails to get from one to another. It takes t_m seconds to get from point a_m to b_m (and back) on the m^\text{th} trail. It takes the same amount of time to get back on the same trail. The competition starts from A and goes to B. There are Q competitors racing. Due to rigging of the race, the q^\text{th} competitor will take the {k_q}^\text{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.

Input Specification

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

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

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

Constraints

For all subtasks: 1 \le A, B \le N, A \ne B and 0 \le t_m \le 10^6

For subtasks 1 and 2: 0 \le M \le \frac{N(N-1)}{2}

For subtasks 3 and 4: 0 \le M \le N \log N

Subtask 1 [20\%]: 2 \le N \le 100 and Q = k_0 = 1

Subtask 2 [20\%]: 2 \le N \le 100 and 1 \le Q, k_q \le 10

Subtask 3 [20\%]: 2 \le N \le 1000 and Q = k_0 = 1

Subtask 4 [40\%]: 2 \le N \le 1000 and 1 \le Q, k_q \le 50

Output Specification

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

5 8 1 5 4
1 2 1
1 3 2
2 3 3
3 4 2
3 5 3
2 4 1
4 5 1
1 5 5
1
2
3
4

Sample Output

3 1
5 1
7 1
-1

Explanation for Sample Output

The trails look like the following:

The fastest path is 1 \rightarrow 2 \rightarrow 4 \rightarrow 5

The second fastest path is 1 \rightarrow 3 \rightarrow 4 \rightarrow 5

The third fastest (slowest) path is 1 \rightarrow 3 \rightarrow 2 \rightarrow 4 \rightarrow 5

A fourth path doesn't exist.

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


Comments


  • 7
    jeffreyxiao  commented on Jan. 8, 2017, 3:06 p.m.

    .


  • 0
    jeffreyxiao  commented on Jan. 8, 2017, 1:59 p.m.

    .


    • 0
      aurpine  commented on Jan. 8, 2017, 2:17 p.m. edited

      There could be, and possibly are.


  • 0
    imaxblue  commented on Jan. 7, 2017, 5: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, 5:26 p.m.

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