问题 4068 --Flight 航班4068: Flight 航班
时间限制: 5 Sec 内存限制: 128 MB
提交: 34 解决: 13
[提交][状态][讨论版][命题人:]题目描述
彼得从最近举行的ACM-ICPC世界总决赛回来，却发现他的返程航班被超额预订，他从航班上撞了下来！好吧，至少他没有被航空公司打败，他还收到了一张他想要的任何两个目的地之间的免费航班的代金券。
他已经在计划明年的旅行。他计划在必要时开车旅行，但他可能用他的免费机票旅行一段路程。他要求你帮助他的计划。
他可以为你提供一个由公路连接的城市网络，在两个城市之间购买汽油的费用，以及其中一些城市之间可用航班的清单。帮助彼得找到他从家乡到明年目的地所需花费的最低金额！
输入
第一行列出五个空格分隔的整数n、m、f、s和t，表示城市n（0<n≤50000）、道路m（0≤m≤150000）、航班f（0≤f≤100）、彼得旅行开始城市s（0≤s<n），彼得要去的城市的t（0≤t<n）。（城市的编号从0到n-1）。
第一行后面是m行，每一行描述一条道路。道路描述包含三个间隔整数i、j和c（0≤i，j<n，i≠j和0<c≤50000），表示存在一条连接城市i和j的道路，其旅行成本为c美分。道路可在任何方向使用，费用相同。所有道路描述都是唯一的。
下列f行中的每一行都包含对可用航班的描述，该描述由两个空间分隔整数u和v（0≤u，v<n，u≠v）组成，表示从城市u到城市v的航班可用（除非在其他地方列出，否则从v到u的航班不可用）。所有航班描述都是唯一的。
输出
输出彼得从家乡到比赛所需花费的最小分，最多使用一个航班。你可以假设彼得总有一条路可以到达目的地。
样例输入
8 11 1 0 5
0 1 10
0 2 10
1 2 10
2 6 40
6 7 10
5 6 10
3 5 15
3 6 40
3 4 20
1 4 20
1 3 20
4 7
样例输出
45
提示
来源
[提交][状态]