Mock CCO '17 Day 2 P2 - Blitzkrieg

View as PDF

Submit solution

Points: 17 (partial)
Time limit: 1.4s
Memory limit: 256M

Problem type

imaxblue has successfully killed Fuehrer King Bradley, but he must now escape. His time machine requires a lightning storm to gain enough energy. There are N cities in Amestris and M roads. imaxblue is located in city A and the time machine is in city B. There are D days before the lightning storm, on which imaxblue must be located in city B. In addition, imaxblue would like to make sure that there are at least K distinct paths to city B, to make it harder for the Amestris army to track him. Unfortunately, each road has an alertness level. Note that imaxblue must change take a road each day, or the Amestris army will catch up to him.

imaxblue would like to know the minimum alertness level he is required to pass in order to have K distinct paths of length D from A to B, or -1 if it is impossible.


For all cases, N\le100, M\le10\,000, D, K\le10^9.
For 4 points, D, K=1.
For additional 2 points N, M, D, K \le 10.
For additional 4 points D \le 10.

Input Specification

Line 1: N, M, D, K, A and B.
Next M lines: 3 integers, x, y and w, representing a bidirectional path from x to y with alertness w.
Note: There may be multiple paths between two nodes.

Sample Input

3 5 6 3 0 2
0 1 5
0 0 4
1 2 1
1 2 6
0 2 12

Sample Output



There are no comments at the moment.