P3821 Isaac

Ju Runguo got hooked on a game, The Binding of Isaac: Rebirth. He has reached the final level, which requires special movement techniques. 1. Starting from time $0$, he must control Isaac to go from the start to the finish. 2. He can arrive at the finish only exactly at time $k$. (Moving from one room to another costs one time unit. His hands are fast, so he never waits in the same room. Isaac may move back and forth among rooms.) 3. If rooms $u$ and $v$ are connected, he can control Isaac to traverse the passage between them if and only if Isaac’s health is at least $f(u, v)$. 4. There are monsters roaming among these rooms. 5. To play it safe, Ju Runguo found a decoder online and discovered in the code that the monsters roam rooms with a fixed pattern: each time they move from one room to another (also costing one time unit), and they always roam within several fixed rooms in a fixed order. The number of rooms in the roaming cycle is $T$. To avoid making mistakes while playing, Ju Runguo hopes to avoid all monsters and reach the finish, i.e., pass the final level without taking damage, and he hopes you can find the minimum health Isaac needs under his control to complete this task. If you cannot solve it, then just tell him openly: 'IMP0SSBLE!!'. He definitely won't kill you.

Determine whether Ju Runguo can pass the final level without taking damage under the above conditions. If he can, output the minimum required health $B$ for Isaac under Ju Runguo’s control; otherwise, output 'IMP0SSBLE!!'.

The first line contains five numbers $n, m, s, t, k$, representing that there are $n$ rooms in total, $m$ pairs of adjacent rooms together with the required health to traverse them, the start is $s$, the finish is $t$, and Isaac must arrive exactly at time $k$. Each of the next $m$ lines contains three numbers $u, v, w$, meaning that room $u$ and room $v$ are adjacent, and the required health to traverse between the two rooms in both directions is $w$. The next line contains a single number $a$, the number of monsters. Then follow $a$ data blocks, each describing one monster’s roaming pattern. In each block, the first number $T$ is the number of rooms in the monster’s roaming cycle, followed by $T$ room IDs that indicate that starting from time $0$, the monster will move from the first room in order and periodically repeat the sequence.

Output a single line: the minimum required health $B$ for Isaac under Ju Runguo’s control, or 'IMP0SSBLE!!'.

There are $20$ groups of testdata. For $15\%$ of the testdata, $a = 0$, $k \leq 20$. For $25\%$ of the testdata, $a \leq 3$, $k \leq 1500$. For $50\%$ of the testdata, $a \leq 3$, $k \leq 10^4$. For $70\%$ of the testdata, $a \leq 20$, $k \leq 10^6$. For $85\%$ of the testdata, $a \leq 30$, $k \leq 10^8$. For $100\%$ of the testdata, $a \leq 30$, $k \leq 2*10^9$, $2 \leq T \leq 4$, $n \leq 50$, $m \leq 1250$. All inputs are within the range of int. All numbers are positive. There may be multiple edges; if an edge is given multiple times, the weight of its last occurrence prevails. Translated by ChatGPT 5