题目描述
Alice 和 Bob 现在要乘飞机旅行，他们选择了一家相对便宜的航空公司。该航空公司一共在 nnn 个城市设有业务，设这些城市分别标记为 000 到 n−1n-1n−1，一共有 mmm 种航线，每种航线连接两个城市，并且航线有一定的价格。
Alice 和 Bob 现在要从一个城市沿着航线到达另一个城市，途中可以进行转机。航空公司对他们这次旅行也推出优惠，他们可以免费在最多 kkk 种航线上搭乘飞机。那么 Alice 和 Bob 这次出行最少花费多少？
输入格式
第一行三个整数 n,m,kn,m,kn,m,k，分别表示城市数，航线数和免费乘坐次数。
接下来一行两个整数 s,ts,ts,t，分别表示他们出行的起点城市编号和终点城市编号。
接下来 mmm 行，每行三个整数 a,b,ca,b,ca,b,c，表示存在一种航线，能从城市 aaa 到达城市 bbb，或从城市 bbb 到达城市 aaa，价格为 ccc。
输出格式
输出一行一个整数，为最少花费。
数据规模与约定
对于 30%30\%30% 的数据，2≤n≤502 \le n \le 502≤n≤50，1≤m≤3001 \le m \le 3001≤m≤300，k=0k=0k=0。
对于 50%50\%50% 的数据，2≤n≤6002 \le n \le 6002≤n≤600，1≤m≤6×1031 \le m \le 6\times10^31≤m≤6×103，0≤k≤10 \le k \le 10≤k≤1。
对于 100%100\%100% 的数据，2≤n≤1042 \le n \le 10^42≤n≤104，1≤m≤5×1041 \le m \le 5\times 10^41≤m≤5×104，0≤k≤100 \le k \le 100≤k≤10，0≤s,t,a,b<n0\le s,t,a,b < n0≤s,t,a,b<n，a≠ba\ne ba=b，0≤c≤1030\le c\le 10^30≤c≤103。
另外存在一组 hack 数据。
思路
考虑dij算法，对于满足两点之间有路径连接的点 aaa 到点 bbb，有两种可能的转移方法：
- ansb←min(ansb,ansa+dis(a,b))ans_b \gets \min(ans_b,ans_a+dis(a,b))ansb←min(ansb,ansa+dis(a,b))，其中 dis(a,b)dis(a,b)dis(a,b) 表示 (a,b)(a,b)(a,b) 间路径距离。
- ansb←min(ansb,ansa)ans_b \gets \min(ans_b,ans_a)ansb←min(ansb,ansa)，当到 aaa 点时免费飞行次数还没被用完的时候可以这样转移。
为了记录到点 aaa 运用 ccc 次免费飞行的最小花费，我们在 ansansans 上引入新变量，记作 ansa,cans_{a,c}ansa,c，表示从出发点飞到 aaa 点的最小花费。可以证明，对于 c1>c2c_1>c_2c1>c2,ansa,c1≤ansa,c2ans_{a,c_1} \leq ans_{a,c_2}ansa,c1≤ansa,c2。最后搜到 anst,kans_{t,k}anst,k 停止就可以。
当然也可以采取分层图的方法，也就是将图分成 k+1k + 1k+1 份，相邻两个图之间边权为 000，按照原有方法运行 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;
}