P4568 [JLOI2011] 飞行路线
Tag：最短路、分层图
题目描述
Alice 和 Bob 现在要乘飞机旅行， 他们选择了一家相对便宜的航空公司。 该航空公司一共在 \(n\) 个城市设有业务， 设这些城市分别标记为 \(0\) 到 \(n-1\)，一共有 \(m\) 种航线， 每种航线连接两个城市，并且航线有一定的价格。
Alice 和 Bob 现在要从一个城市沿着航线到达另一个城市， 途中可以进行转机。航空公司对他们这次旅行也推出优惠， 他们可以免费在最多 \(k\) 种航线上搭乘飞机。 那么 Alice 和 Bob 这次出行最少花费多少？
数据说明：
\(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\)。
分析
分层图板子题，详情见 分层图。
代码实现
typedef pair<int,int> PII;
void IHaveNoLimitation() {
int n, m, k;
cin >> n >> m >> k;
int s, t;
s = 1,t = n;
vector<vector<PII>> adj((k + 1) * n + 5);
for (int i = 0; i < m; ++i) {
int u, v, w;
cin >> u >> v >> w;
adj[u].push_back({v, w});
adj[v].push_back({u, w});
for (int j = 1; j <= k; ++j) {
adj[(j - 1) * n + u].push_back({j * n + v, 0});
adj[(j - 1) * n + v].push_back({j * n + u, 0});
adj[j * n + u].push_back({j * n + v, w});
adj[j * n + v].push_back({j * n + u, w});
}
}
vector<int> dis((k + 1) * n + 5,INT_MAX), vis((k + 1) * n + 5);
auto dijkstra = [&](int s) {
dis[s] = 0;
priority_queue<PII, vector<PII>, greater<PII>> pq;
pq.push({0, s});
while (!pq.empty()) {
auto [w, cur] = pq.top();
pq.pop();
if (vis[cur]) continue;
vis[cur] = 1;
for (auto &nxt: adj[cur]) {
auto &[to, val] = nxt;
if (dis[to] > dis[cur] + val) {
dis[to] = dis[cur] + val;
pq.push({dis[to], to});
}
}
}
};
dijkstra(s);
int ans = INT_MAX;
for (int i = 0; i <= k ; i++) {
ans = min(ans,dis[i * n + t]);
}
cout << ans << endl;
}
日志
本页面创建于 2025/12/04 15:33