把免费次数作为分层状态，在 n(k+1) 个状态上运行 Dijkstra。
OJ: luogu
题目 ID: P4568
难度:提高
标签:分层图Dijkstra状态扩展python
日期: 2026-07-17 03:00
题意
无向图中最多让 k 条边免费，求起点到终点的最低花费。
思路
状态 (city, used) 表示已使用 used 次免费机会。走一条边既可付费留在本层，也可花一次机会以 0 代价进入下一层；所有新边权仍非负，直接运行 Dijkstra。
Python 知识
- 二维列表
distance[used][city]对应分层图。 - 堆元组
(cost, city, used)自然按费用排序。 min(layer[target] for layer in distance)允许免费次数少于k。
代码
python
import sys
from heapq import heappop, heappush
input = sys.stdin.buffer.readline
n, edges, free_limit = map(int, input().split())
start, target = map(int, input().split())
graph = [[] for _ in range(n)]
for _ in range(edges):
u, v, price = map(int, input().split())
graph[u].append((v, price))
graph[v].append((u, price))
infinity = 10**30
distance = [[infinity] * n for _ in range(free_limit + 1)]
distance[0][start] = 0
heap = [(0, start, 0)]
while heap:
current, node, used = heappop(heap)
if current != distance[used][node]:
continue
for neighbor, price in graph[node]:
candidate = current + price
if candidate < distance[used][neighbor]:
distance[used][neighbor] = candidate
heappush(heap, (candidate, neighbor, used))
if used < free_limit and current < distance[used + 1][neighbor]:
distance[used + 1][neighbor] = current
heappush(heap, (current, neighbor, used + 1))
print(min(layer[target] for layer in distance))原有 C++ 版本仍保留：
cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 10000 + 5;
const int MAXM = 50000 * 2 + 5;
const long long INF = (1LL << 60);
struct HeapNode {
int u;
int used;
long long dist;
bool operator < (const HeapNode &other) const {
return dist > other.dist;
}
};
int n, m, k;
int s, t;
int head[MAXN], to[MAXM], nxt[MAXM], w[MAXM], edge_cnt;
long long dist_arr[MAXN][15];
bool vis[MAXN][15];
void init_graph() {
edge_cnt = 0;
for (int i = 0; i < n; i++) {
head[i] = 0;
}
}
void add_edge(int u, int v, int len) {
edge_cnt++;
to[edge_cnt] = v;
w[edge_cnt] = len;
nxt[edge_cnt] = head[u];
head[u] = edge_cnt;
}
void dijkstra() {
for (int i = 0; i < n; i++) {
for (int j = 0; j <= k; j++) {
dist_arr[i][j] = INF;
vis[i][j] = false;
}
}
priority_queue<HeapNode> pq;
dist_arr[s][0] = 0;
pq.push({s, 0, 0});
while (!pq.empty()) {
HeapNode cur = pq.top();
pq.pop();
int u = cur.u;
int used = cur.used;
if (vis[u][used]) {
continue;
}
vis[u][used] = true;
for (int i = head[u]; i != 0; i = nxt[i]) {
int v = to[i];
long long nd = dist_arr[u][used] + w[i];
if (nd < dist_arr[v][used]) {
dist_arr[v][used] = nd;
pq.push({v, used, nd});
}
// 这条航线可以免费坐一次，相当于跳到下一层且不增加代价。
if (used < k && dist_arr[u][used] < dist_arr[v][used + 1]) {
dist_arr[v][used + 1] = dist_arr[u][used];
pq.push({v, used + 1, dist_arr[v][used + 1]});
}
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m >> k;
cin >> s >> t;
init_graph();
for (int i = 1; i <= m; i++) {
int u, v, len;
cin >> u >> v >> len;
add_edge(u, v, len);
add_edge(v, u, len);
}
dijkstra();
long long answer = INF;
for (int used = 0; used <= k; used++) {
if (dist_arr[t][used] < answer) {
answer = dist_arr[t][used];
}
}
cout << answer << '\n';
return 0;
}复杂度
时间 O(k(n+m)log(kn))，空间 O(kn+m)。
总结
“最多使用若干次能力”通常把使用次数加入状态分层。