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