F.A.Q
Hand In Hand
Online Acmers
Problem Archive
Realtime Judge Status
Authors Ranklist

C/C++/Java Exams
ACM Steps
Go to Job
Contest LiveCast
ICPC@China
Best Coder beta
VIP | STD Contests
DIY | Web-DIY beta
Register new ID

# Andy and Maze

Time Limit: 15000/15000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 962    Accepted Submission(s): 340

Problem Description
Andy is a famous explorer at Nanjing University second to none. One day he was trapped in a maze. The maze consisted of several rooms, and there was a precious gem in each room. There were also some bidirectional roads connecting some pairs of these rooms. It took some time to travel along the road in either direction.

Andy was in a room, but he didn't know which room he was in. Suddenly, he heard a low voice, saying that, "if you want to get out of the maze, you must collect $k$ gems." Andy wanted to know, what was the maximum possible time to get out of the maze, or it was impossible at all? Note that he couldn't visit the same room more than once.

Input
The first line of input consists of a single integer $T$ $(1 \leq T \leq 35)$, denoting the number of test cases. Each test case starts with a line of three integers $n, m, k$ $(2 \leq n \leq 10^4, 1 \leq m \leq 10^4, 2 \leq k \leq 6)$, denoting the number of rooms and the number of roads in the maze, and the number of gems he needed to collect, respectively. Each of the next $m$ lines contains three intergers $u, v, t$ $(1 \leq u, v \leq n, u \neq v, 1 \leq t \leq 10^8)$, specifying a road connecting the $u$th and the $v$th rooms, which took $t$ minutes to travel in either direction. No two roads connected the same pair of rooms.
There are at most 5 test cases with $\max\{n, m\} > 100$.

Output
For each test case, print the maximum possible time in minute to get out of the maze in one line. If it was impossible to get out of the maze, print $\texttt{impossible}$ instead.

Sample Input
2
4 4 3
1 2 6
2 3 1
2 4 4
1 4 5
5 3 4
1 2 2
2 3 3
4 5 5

Sample Output
11
impossible

Source

Statistic | Submit | Discuss | Note
 Home | Top Hangzhou Dianzi University Online Judge 3.0 Copyright © 2005-2023 HDU ACM Team. All Rights Reserved. Designer & Developer : Wang Rongtao LinLe GaoJie GanLu Total 0.000000(s) query 1, Server time : 2023-06-01 00:25:58, Gzip enabled Administration