洛谷 P4568 飞行路线（分层图最短路）

[JLOI2011] 飞行路线

题目描述

Alice 与 Bob 计划乘坐飞机出行，他们选择了一家价格较为实惠的航空企业。这家航空公司在 n 个城市开展业务，这些城市分别被编号为 0 到 n-1，同时设有 m 条航线，每条航线连接两个城市，并且每条航线都对应着一定的费用。现在 Alice 与 Bob 需要从一个城市出发，通过航线抵达另一个城市，在此过程中可以进行多次转机。此外，航空公司还为此次行程推出了优惠活动，允许他们最多在 k 条航线上享受免费搭乘的待遇。那么，在这种条件下，Alice 与 Bob 此次出行所需的最低费用是多少？

输入格式

输入的第一行包含三个整数 n,m,k，依次代表城市数量、航线总数以及可享受免费乘坐的次数。

随后的一行给出两个整数 s,t，分别对应出行的起始城市编号与目标城市编号。

接下来的 m 行中，每一行都包含三个整数 a,b,c，用于描述一种双向航线，即从城市 a 可以抵达城市 b，或者从城市 b 可以抵达城市 a，且该航线的费用为 c。

输出格式

输出一个整数，表示所需的最低费用。

样例分析与呈现

样例输入 #1

    5 6 1
    0 4
    0 1 5
    1 2 5
    2 3