題目描述

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;
}