145. Strange People
time limit per test: 0.25
sec. memory limit per test: 4096
KB
Once upon a time in one kingdom lives strange people.
In this kingdom to travel from city to city there was
a taxes.
But people don't want to travel cheaper from one place
to another. They want to travel from place to place by
Kth simple expensive path betwen this cites.
Your task is to find how much money they must prepare
to go from one given city to another (also given) if
they travel using K'th simple expensive path between
these two cites. And you must print that path. (if
there exist many solutions output any of them)
It is guarantee that K'th expensive path between this
cites exist. If there is road between city X and Y
than there is road between Y and X.
Between two cites exists no more than 1 road.
4 <= N  number of cites <= 100
M  number od roads
1 <= taxes bewtween two cites <= 10000
1 <= K  the K'th expensive path to find <= 500
Input
N M K
x y mon 
x y mon 
...  M lines
x y mon 
xs xe
where xs is start city and xe is end city
x and y is pairs of integer that are numbers of two
cites and mon is tax between this cites
Output
Z dc
x1 x2 x3 x4 .. xn
where Z is the cost of the K'th expensive path and
x1 x2 ... xn is the path
dc is number of cites in (x1 x2 x3 ... xn)
Sample Input
5 10 3
1 2 6
1 3 13
1 4 18
1 5 35
2 3 14
2 4 34
2 5 17
3 4 22
3 5 15
4 5 34
1 5
Sample Output
35 2
1 5
Some explanations to Sample Test case:
This are all paths beteen 1 and 5 and their costs
1 2 5 > 23
1 3 5 > 28
1 2 3 5 > 35
1 5 > 35
1 3 2 5 > 44
1 4 5 > 52
1 4 3 5 > 55
1 3 4 5 > 69
1 4 2 5 > 69
1 4 3 2 5 > 71
1 2 4 5 > 74
1 2 3 4 5 > 76
1 2 4 3 5 > 77
1 4 2 3 5 > 81
1 3 4 2 5 > 86
1 3 2 4 5 > 95
if there exist q or more paths with equal cost than if
first of them is K'th expensive path then some of
others q  1 cites is (K + 1)'th expensive path and so
on..
Example in Sample test paths 1 2 3 5 and 1 5 have
equal cost so
3'th expensive path is 35 and 3'th expensive path may
be 1 5 or 1 2 3 5
and
4'th expesnive path is 35 and 4'th expensive path may
be 15 or 1 2 3 5
