409376: GYM103495 B Among Us

Among Us is an online multiplayer social deduction game developed and published by American game studio Innersloth. Dropped into a spaceship, each player is designated as a private role of either a crewmate or an impostor. In this problem, there are exactly $$$2$$$ imposters and at most $$$8$$$ crewmates. The imposters need to kill all the crewmates to win the game, while the crewmates need to complete the tasks as quickly as possible.

There are $$$n$$$ rooms in the game map. When the game begins, each player will spawn in a certain room. Players have two choices for each second: stand still or move to another room. There are $$$m$$$ undirected secret paths for imposters to move, each of which connects two rooms and takes a certain amount of time to pass through. In this problem, the crewmates can move freely among the rooms, while the imposters can only use the $$$m$$$ secret paths.

As the imposters are extremely smart, they can predict where some crewmates will be at some moments. When a crewmate appears in a room as predicted and at least one imposter is there, the imposter can kill the crewmate without consuming time. The imposters also predict that the crewmates will finish all the tasks in $$$t_{\max}$$$ seconds. That is, if at least one crewmate survives after $$$t_{\max}$$$ seconds, the imposters will lose the game. Based on the prediction, please calculate the minimum time for the imposters to kill all the crewmates if possible.

The first line of the input contains a single integer $$$T$$$ ($$$1 \leq T \leq 100$$$), denoting the number of test cases.

The first line of each test case contains three integers $$$n,m,k$$$ ($$$1 \leq n \leq 10^4$$$, $$$1 \leq m \leq 2 \times 10^4$$$, $$$1 \leq k \leq 8$$$), denoting the number of rooms, secret paths, and crewmates respectively.

Each of the next $$$m$$$ lines contains three integers $$$u,v,w$$$ ($$$1 \leq u$$$, $$$v \leq n$$$, $$$u \neq v$$$, $$$1 \leq w \leq 10^4$$$), denoting there is a secret path connecting room $$$u$$$ and $$$v$$$, and imposters need exactly $$$w$$$ seconds to pass through it.

The next line contains two integers $$$e$$$ and $$$t_{\max}$$$ ($$$1 \leq e \leq 10^5$$$, $$$1 \leq t_{\max} \leq 10^8$$$), denoting the number of predictions and the time for the crewmates to complete all the tasks.

Each of the next $$$e$$$ lines contains three integers $$$p, x, t$$$ ($$$1 \leq p \leq k$$$, $$$1 \leq x \leq n$$$, $$$1 \leq t \leq t_{\max}$$$), denoting the crewmate $$$p$$$ will appear in room $$$x$$$ at $$$t$$$ seconds after the game begins.

The last line of each test case contains two integers $$$x$$$ and $$$y$$$ ($$$1 \leq x, y \leq n$$$), denoting that the two imposters will spawn in room $$$x$$$ and $$$y$$$ when the game begins.

It's guaranteed that $$$\sum n \leq 10^4$$$, $$$\sum m \leq 2 \times 10^4$$$ and $$$\sum e \leq 10^5$$$ over all test cases.

For each test case, output the minimum time for the imposters to kill all the crewmates in a single line. If the imposters can't win the game, output $$$-1$$$ in a single line.

4
5 7 3
1 2 1
2 3 2
2 4 1
3 4 5
4 5 1
5 2 5
5 1 5
3 8
1 5 3
3 4 2
2 2 4
3 1
3 1 2
1 2 1
3 3
1 2 1
2 2 1
1 2 2
2 3
3 1 2
1 2 1
3 3
1 2 1
2 2 1
1 2 2
3 3
10 10 8
1 2 1
2 3 1
3 4 1
4 5 1
5 6 1
6 7 1
7 8 1
8 9 1
9 10 1
10 1 1
8 10
1 2 1
2 3 2
3 4 3
4 5 4
5 7 1
6 8 2
7 9 3
8 10 4
1 6

4
1
-1
4