P4568 [JLOI2011] 飛行路線

題目描述

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

輸出格式

輸出一行一個整數，為最少花費。

輸入輸出樣例 #1

輸入 #1

5 6 1
0 4
0 1 5
1 2 5
2 3 5
3 4 5
2 3 3
0 2 100

輸出 #1

8

說明/提示

數據規模與約定

對于 $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 數據。

對于這題，看似與 P1948 [USACO08JAN] Telephone Lines S 十分相像，都是在 k 次特殊機會下求最短路。但稍微有點不同。P1948 需要最小化最長邊，故其二分時的 check 相對簡單，可以采取二分策略。但本題要求最小化路徑，此時的 check 變為了能否在總花費不超過 mid 的情況下從 s 到達 t ，難度幾乎和原問題一樣。故我們可以考慮利用分層圖，將使用過的免費次數used_k 加入路徑狀態中，在尋最短路時更新兩種狀態：使用免費次數和不使用免費次數。最后從所有 used_k 中找到到 t 的最短路。

#include<bits/stdc++.h>
using namespace std;const int INF = INT_MAX;int main(){int n, m, k, s, t;cin >> n >> m >> k >> s >> t;vector<vector<pair<int, int>>> g(n);for(int i = 0; i < m; i++){int a, b, c;cin >> a >> b >> c;g[a].emplace_back(b, c);g[b].emplace_back(a, c);}vector<vector<int>> dist(n, vector<int>(k+1, INF));priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<>> pq;dist[s][0] = 0;pq.emplace(0, s, 0);while(!pq.empty()){auto [d, u, used_k] = pq.top();pq.pop();if(d > dist[u][used_k]) continue;for(auto i : g[u]){int v = i.first;int w = i.second;if(dist[u][used_k] + w < dist[v][used_k]){dist[v][used_k] = dist[u][used_k] + w;pq.emplace(dist[v][used_k], v, used_k); }if(used_k < k){if(dist[u][used_k] < dist[v][used_k+1]){dist[v][used_k+1] = dist[u][used_k];pq.emplace(dist[v][used_k+1], v, used_k+1);}}}}int ans = INF;for(int i = 0;i<=k;i++){if(dist[t][i]<ans) ans = dist[t][i];}cout<<ans;return 0;
}