题目描述

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

输出格式

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

数据规模与约定

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

对于 $50\%$ 的数据，$2\le n\le 600$，$1\le m\le 6\times 10^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$。

另外存在一组 hack 数据。

思路

考虑dij算法，对于满足两点之间有路径连接的点 $a$ 到点 $b$，有两种可能的转移方法：

• $an{s}_b\leftarrow \min (an{s}_b,an{s}_a+dis(a,b))$，其中 $dis(a,b)$ 表示 $(a,b)$ 间路径距离。
• $an{s}_b\leftarrow \min (an{s}_b,an{s}_a)$，当到 $a$ 点时免费飞行次数还没被用完的时候可以这样转移。

为了记录到点 $a$ 运用 $c$ 次免费飞行的最小花费，我们在 $ans$ 上引入新变量，记作 $an{s}_{a,c}$，表示从出发点飞到 $a$ 点的最小花费。可以证明，对于 $c_1>c_2$,$an{s}_{a,c_1}\le an{s}_{a,c_2}$。最后搜到 $an{s}_{t,k}$ 停止就可以。

当然也可以采取分层图的方法，也就是将图分成 $k+1$ 份，相邻两个图之间边权为 $0$，按照原有方法运行 dij 算法也可以。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,k;
int s,t;
int head[10005],nex[100005],to[100005],w[100005],cnt = 0; 
int ans[10005][15];
inline void add(int x,int y,int z) {nex[++cnt] = head[x];head[x] = cnt;to[cnt] = y;w[cnt] = z;
}
struct node {int id,w,k;friend bool operator <(node x,node y) {if(x.w != y.w) return x.w > y.w;if(x.k != y.k) return x.k > y.k;return x.id > y.id;}
};
priority_queue<node>dij;
inline void ps(int id,int w,int k_1) {node p;p.id = id;p.w = w;p.k = k_1;dij.push(p);for(int i = k_1;i <= k and ans[id][i] > w;i++) {ans[id][i] = min(ans[id][i],w);}
}
signed main() {scanf("%lld %lld %lld",&n,&m,&k);scanf("%lld %lld",&s,&t);for(int i = 0;i < n;i++) {if(i == s) continue;for(int j = 0;j <= k;j++) {ans[i][j] = 100000000000;}}for(int i = 1;i <= m;i++) {int x,y,z;scanf("%lld %lld %lld",&x,&y,&z);add(x,y,z),add(y,x,z);}ps(s,0,0);while(!dij.empty()) {node p = dij.top();dij.pop();if(ans[p.id][p.k] < p.w) continue;//printf("______%lld %lld %lld\n",p.id,p.w,p.k);if(p.id == t and (p.k == k or p.w == 0)) {printf("%lld\n",p.w);return 0;}for(int i = head[p.id];i;i = nex[i]) {if(p.k < k) {if(ans[to[i]][p.k + 1] > p.w) {ps(to[i],p.w,p.k + 1);		}} if(ans[to[i]][p.k] + w[i] > p.w) {ps(to[i],p.w + w[i],p.k);		}}}return 0;
}