Mock CCO '17 Day 2 P2 - Blitzkrieg

View as PDF

Submit solution

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

Author:
Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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.

Subtasks

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

5

Comments

There are no comments at the moment.