题意描述

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$。

输出格式

输出数据仅有一行，包含一个整数$ans$，为最少花费的钱数。

Input & Output ‘s examples

Input ‘s eg

Output ‘s eg

数据范围与约定

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

对于$50\%$的数据,$2 \le n \le 600,1 \le m \le 6000,0 \le k \le 1$;

对于$100\%$的数据,$2 \le n \le 10000,1 \le m \le 50000,0 \le k \le 10$

分析

分层图最短路的版子题。

30分做法

设起点为$start$,终点为$finish$。

对于$30\%$的数据，$k = 0$，则我们直接使用$Dijkstra$算法求解从$start$到$finish$的最短路即可。

~~10年前的省选暴力分都是白送的吗？？？~~

100分做法

考虑如何处理免费次数。

我们将图建成$k$层，第$i$层对应着使用了$i$次免费次数。

各层内部正常连边，而上下两层之间从上到下连边权为$0$的边。这样，每跑一层，就相当于用了一次免费机会。

就像下图：

但这样还不够，因为如果提供的免费机会大于坐飞机的次数的话，则花费为$0$。

因此，我们还需要对每一层的$finish$向下一层的$finish$建一条边权为$0$的边。以便于到达终点之后处理剩下的免费次数。

最后，我们只需要跑一次从$start$到$finish + n * k$的最短路即可。

剩下的详见代码注释。

Code[Accepted]

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<stack>
#include<queue>
#include<deque>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<cstdlib>
#include<cctype>
#include<cmath>

#define ll long long
#define I inline
#define M 125001
#define K 10

using namespace std;

int n , m , s , k;

struct Edge{
    int to;
    int last;
    ll dis;
}edge[(M * K) << 1];    //每一层都要建m条边，并且题目中要求是双向边，因此，总边数为(m * k) * 2

int head[(M * K) << 1];
int edge_num;

I void add_edge(int from , int to , ll dis){
    edge[++ edge_num] = Edge{to , head[from] , dis};
    head[from] = edge_num;
}

ll dis[(M * K) << 1];
bool vis[(M * K) << 1];

void Dijkstra(int s){
    #define pairs pair<ll , ll >

    priority_queue<pairs , vector<pairs > , greater<pairs > > Q;
    for(int i = 0; i <= M; i ++){
        dis[i] = 0x3f3f3f3f; 
    }
    dis[s] = 0;
    Q.push(make_pair(dis[s] , s));
    while(!Q.empty()){
        int v = Q.top().second;
        Q.pop();
        if(vis[v]){
            continue;
        }
        vis[v] = true;
        for(int i = head[v]; i ; i = edge[i].last){
            int to = edge[i].to;
            if(dis[to] > dis[v] + edge[i].dis){
                dis[to] = dis[v] + edge[i].dis;
                Q.push(make_pair(dis[to] , to));
            }
        }
    }
}

int main(){
    int u , v , w;
    int start , finish;
    cin >> n >> m >> k;
    cin >> start >> finish;
    for(int i = 0; i < m; i ++){
        cin >> u >> v >> w;
        add_edge(u , v , w);
        add_edge(v , u , w);
        for(int j = 1; j <= k; j ++){   //对于每一层，分别建边
            add_edge(u + (j - 1) * n , v + j * n , 0);  //与下一层建立两条边权为0的边
            add_edge(v + (j - 1) * n , u + j * n , 0);
            add_edge(u + j * n , v + j * n , w);    //在本层中直接建边
            add_edge(v + j * n , u + j * n , w);
        }
    }
    for(int i = 1; i <= k; i ++){   //最后在每一个结束点之间分别建一条边权为0的边，方便处理没用完的免费次数。
        add_edge(finish + (i - 1) * n , finish + i * n , 0);
    }
    Dijkstra(start);
    cout << dis[finish + k * n] << "\n";
    return 0;
}