Logo Universal Online Judge

UOJ

时间限制:1 s 空间限制:32 MB

#757. 神奇的跑鞋

Statistics

放假了,nsoi的同学准备回家,学校和家之间有许多的城镇(按1到N编号,学校也看成城镇),城镇与城填之间有道路连通。小S的家就位于某个城镇。现在小S想尽快回家,所以他会走一条最短路回家。不过小S还有一双神奇的跑鞋,(它可以让小S从一个城镇到另一个不花时间(可以把距离看成0),当然跑鞋的能量是有限的,他最多可以用3次)。现在要你解决的是小s回家所走过的最短距离。
输入:
第一行四个整数(N,S,H,T)表示点的个数(N<=400),学校的编号,家的编号,以及跑鞋使用的次数。
接下来M行,每行3个数,A,B,C表示A、B城镇的距离为C。
输出:
一个数表示最短距离,不通输出-1.
样例:
输入:
3 1 3 1
1 2 5
1 3 100
2 3 1
输出:
0