Flight Route

Problem Statement

Alice 和 Bob 现在要乘飞机旅行，他们选择了一家相对便宜的航空公司。该航空公司一共在 $n$ 个城市设有业务，设这些城市分别标记为 $0$ 到 $n-1$，一共有 $m$ 种航线，每种航线连接两个城市，并且航线有一定的价格。

Alice 和 Bob 现在要从一个城市沿着航线到达另一个城市，途中可以进行转机。航空公司对他们这次旅行也推出优惠，他们可以免费在最多 $k$ 种航线上搭乘飞机。那么 Alice 和 Bob 这次出行最少花费多少？

Input

第一行三个整数 $n,m,k$，分别表示城市数，航线数和免费乘坐次数。

接下来一行两个整数 $s,t$，分别表示他们出行的起点城市编号和终点城市编号。

接下来 $m$ 行，每行三个整数 $a,b,c$，表示存在一种航线，能从城市 $a$ 到达城市 $b$，或从城市 $b$ 到达城市 $a$，价格为 $c$。

Output

输出一行一个整数，为最少花费。

Sample Input

Sample Output

1

8

Constraints

对于 $30%$ 的数据，$2 \le n \le 50$，$1 \le m \le 300$，$k=0$。

对于 $50%$ 的数据，$2 \le n \le 600$，$1 \le m \le 6\times10^3$，$0 \le k \le 1$。

对于 $100%$ 的数据，$2 \le n \le 10^4$，$1 \le m \le 5\times 10^4$，$0 \le k \le 10$，$0\le s,t,a,b < n$，$a\ne b$，$0\le c\le 10^3$。

Solving

分层图最短路的模板题。

分层思想核心

分层图最短路的核心思想是将原图复制层（这里是可使用的特殊操作次数），每一层代表使用了不同数量特殊操作（免费通行券）的状态。

具体来说：

第0层表示没有使用任何免费通行券的状态。
第1层表示使用了1张免费通行券的状态。
… …
第k层表示使用了k张免费通行券的状态。

每一层都是一个完整的图，节点和边的结构与原图相同。不同层之间通过特殊的边连接，这些边表示使用特殊操作（免费通行券）从一层转移到另一层。

在Dijkstra的状态转移中，我们可以在有券的情况下选择使用免费通行券或者不使用，分两种情况转移即可。

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115


#include <bits/stdc++.h>
#define int long long
#define endl '\n'
#define INF 0x3f3f3f3f
#define NINF -0x3f3f3f3f
#define Single
using namespace std;
using ll = long long;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int N = 10010;
const int M = 1e5+10;
int cnt = 0;
int head[N];
int dis[N][11];//second dimension is the ticket for use
bool vis[N][11];
int n,m,k,s,t;
struct Edge
{
    int to,next,w;
}edge[M];
struct node
{
    int path;
    int pos;
    int usedtickets;
    bool operator<(const node &other) const
    {
        return path > other.path;
    }
};
priority_queue<node> q;
void add(int u,int v,int w)
{
    cnt++;
    edge[cnt].to = v;
    edge[cnt].w = w;
    edge[cnt].next = head[u];
    head[u] = cnt; 
}
void init(int n)
{   
    memset(vis,false,sizeof vis);
    for(int i=0;i<=n;i++)
    {
        for(int j=0;j<=k;j++)
        dis[i][j] = INF;
    }
}
void dijkstra(int start)
{
    dis[start][0] = 0;
    q.push({0,start,0});//third dimension is used tickets 
    while(!q.empty())
    {
        int minnum = q.top().pos;
        int use = q.top().usedtickets;
        q.pop();
        if(vis[minnum][use]) continue;
        vis[minnum][use] = true;
        for(int i=head[minnum];i;i=edge[i].next)
        {
            int v = edge[i].to;
            int w = edge[i].w;
            //use free ticket
            if(use < k)
            {
                if(dis[v][use+1] > dis[minnum][use])
                {
                    dis[v][use+1] = dis[minnum][use];
                    q.push({dis[v][use+1],v,use+1});
                }
            }
            //do not use
            if(dis[v][use]>dis[minnum][use] + w)
            {
                dis[v][use] = dis[minnum][use] + w;
                q.push({dis[v][use],v,use});
            }
        }
    }
}
void solve()
{
    cin >> n >> m >> k >> s >> t;
    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        cin >> u >> v >> w;
        add(u,v,w);
        add(v,u,w);
    }
    init(n);
    dijkstra(s);
    int ans = INF;
    //有可能并未用完k张票，所以要取最小值。
    for(int i=0;i<=k;i++) ans = min(dis[t][i],ans);
    cout << ans;
}

signed main()
{
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
    int T;
#ifdef Single
    T = 1;
#else
    cin >> T;
#endif
    while(T--)
    {
        solve();
    }
    return 0;
}