先从 n 反向 BFS 求各点到 n 的最短边数,再从 1 出发按层在出边里取最小颜色并只保留走完剩余最短路的点,得到字典序最小的颜色序列。
OJ: roj
题目 ID: 1688
难度:提高
标签:图论BFS最短路贪心字典序python
创建: 2026-10-07 15:30
更新: 2026-10-07 15:30
形式化题目
给定无向图
对应颜色序列
- 先最小化边数
; - 在边数取到最小值
的前提下,最小化颜色序列的字典序。
输出
这里出现了两个目标,并且是字典序意义下的两级目标:先把可行解集缩小到"长度 =
正解
思路
第一步:把"长度"这个自由度消掉。 一条路径的颜色序列长度等于它的边数,所以字典序比较
只发生在长度相同的两条路径之间——长度一旦不同,短的直接胜出。于是要先知道
第二步:字典序就是"逐位贪心"。 长度已被钉死为
这条等式就是全部约束:它保证"位号 = 剩余距离",任何满足它的节点都一定能续走到
于是算法是:
- 维护当前层
cur:所有可以作为"某条最优路径第个终点"的节点,它们都满足 ; - 枚举
cur中所有指向的节点的出边,取其中最小颜色 cmin, 它就是答案的第位(因为比它小的颜色在这一位没有任何可行边,而它自己一定可行); - 下一层 = 所有"颜色恰为
cmin、恰为 "的出边终点, 并且每个点只入层一次( in_layer标记)。
第三步:为什么第二位贪心不会破坏第一位? 这是分层贪心最常见的疑问。答案是:
判定"第
为什么每个点只入层一次就够? 层号 in_layer 标记后,
每个点最多被扫出边一次,总扫描量
用题目样例走一遍(
| 层 |
当前层节点 | 候选出边(节点, 颜色) | cmin |
下一层 | |
|---|---|---|---|---|---|
| 0 | 1 | 1 | |||
| 1 | 0 | 3 |
1 3,与样例一致。
注意第 0 层的候选里 1 3;如果只把节点 2 3。这说明"同一对点之间的不同颜色边各自独立成一次转移",
平行边必须全部保留。
关于不连通: 题面没有定义 0 与一个空行。
十组官方数据都不触发这个分支(std.cpp 与本解在此约定上一致)。
代码
Python 版:
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-07 15:30
# update_at: 2026-10-07 15:30
import sys
from collections import deque
UNREACHABLE = -1 # dist 里的哨兵:该点走不到 n(最短路长度必 >= 0,不会撞车)
# 类型别名(Python 3.12+ 的 type 语句),相当于 C++ 的 using / typedef
type Adj = list[list[tuple[int, int]]] # 邻接表:adj[u] = [(邻居, 边颜色), ...]
def rev_bfs(adj: Adj, n: int) -> list[int]:
"""从 n 反向 BFS,返回每个点到 n 的最短边数(不可达为 UNREACHABLE)。"""
dist = [UNREACHABLE] * (n + 1)
dist[n] = 0
q = deque([n])
while q:
u = q.popleft()
for v, _color in adj[u]:
if dist[v] == UNREACHABLE: # 反向 BFS 首次到达即最短
dist[v] = dist[u] + 1
q.append(v)
return dist
def ideal_path(adj: Adj, dist: list[int]) -> list[int] | None:
"""长度已被最短路钉死,逐层在“能走完剩余最短路”的出边里取最小颜色。
返回 None 表示 1 走不到 n(dist[1] 是 UNREACHABLE),此时没有颜色序列。
"""
total = dist[1]
if total == UNREACHABLE:
return None
seq: list[int] = []
seen = [False] * len(dist) # 每个点至多入层一次,保证总扫描量 O(n + m)
cur = [1]
seen[1] = True
while len(seq) < total:
target = total - len(seq) - 1 # 下一层节点必须满足 dist == target
# 本层所有可行出边的颜色里取最小,就是这一位能取到的最小值
cmin = min(c for u in cur for v, c in adj[u] if dist[v] == target)
seq.append(cmin)
nxt: list[int] = []
for u in cur:
for v, c in adj[u]:
on_best_edge = dist[v] == target and c == cmin # 走它能续完剩余最短路
if on_best_edge and not seen[v]:
seen[v] = True
nxt.append(v)
cur = nxt
return seq
def solve() -> None:
data = iter(map(int, sys.stdin.buffer.read().split()))
out: list[str] = []
T = next(data)
for _ in range(T):
n, m = next(data), next(data)
adj: Adj = [[] for _ in range(n + 1)]
for _ in range(m):
a, b, c = next(data), next(data), next(data)
if a == b:
continue # 自环不可能落在最短路上
adj[a].append((b, c))
adj[b].append((a, c))
dist = rev_bfs(adj, n)
seq = ideal_path(adj, dist)
# 题面未定义不连通,约定输出 0 与空行;可达时输出长度与颜色序列
out += ["0", ""] if seq is None else [str(len(seq)), ' '.join(map(str, seq))]
print('\n'.join(out))
if __name__ == "__main__":
solve()C++ 版(同一算法):
/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-10-07 15:30
* update_at: 2026-10-07 15:30
*/
// main.cpp:两次 BFS 求 1 到 n 的最短路中颜色序列字典序最小的那条。
// 题目数据默认 ll;本题所有量都在 int 范围内(n,m ≤ 2·10^5,颜色 ≤ 10^9),
// 大数组一律用 int,把峰值内存压进 64MB 的时限。
#include <cstdio>
#include <climits>
typedef long long ll;
const int MAXN = 100005; // 点数上限
const int MAXM = 200005 * 2; // 边数上限:一条无向边存两条半边
// 无向图用链式前向星;一个 Edge 就是一条半边,字段聚合在一个 struct 里
struct Edge {
int to; // 这条半边指向的点
int color; // 这条边的颜色
int nxt; // 同一出发点上的下一条半边,0 表示结束
};
Edge edge[MAXM]; // 半边池,edge[i] 是第 i 条半边
int head[MAXN]; // head[u]:从 u 出发的第一条半边编号
int edge_cnt; // 已加入的半边数量
int dist_to_n[MAXN]; // dist_to_n[v]:v 到 n 的最短边数,-1 表示不可达
int in_layer[MAXN]; // in_layer[v]:v 是否已经作为某个最优前缀的终点入层
int queue_bfs[MAXN]; // 反向 BFS 用的手写队列
int cur_layer[MAXN]; // 当前层的节点
int nxt_layer[MAXN]; // 下一层的节点
int out_seq[MAXN]; // 路径上的颜色序列(长度就是最短路长度 D)
// 加入一条无向边,两个方向各存一条半边
void add_edge(int u, int v, int c) {
edge_cnt++;
edge[edge_cnt].to = v;
edge[edge_cnt].color = c;
edge[edge_cnt].nxt = head[u];
head[u] = edge_cnt;
edge_cnt++;
edge[edge_cnt].to = u;
edge[edge_cnt].color = c;
edge[edge_cnt].nxt = head[v];
head[v] = edge_cnt;
}
// 从 n 反向 BFS,求出每个点到 n 的最短边数
void bfs_reverse(int n) {
for (int i = 1; i <= n; i++) dist_to_n[i] = -1;
int q_head = 0, q_tail = 0;
dist_to_n[n] = 0;
queue_bfs[q_tail++] = n;
while (q_head < q_tail) {
int u = queue_bfs[q_head++];
for (int e = head[u]; e != 0; e = edge[e].nxt) {
int v = edge[e].to;
if (dist_to_n[v] == -1) { // 反向 BFS 首次到达即最短
dist_to_n[v] = dist_to_n[u] + 1;
queue_bfs[q_tail++] = v;
}
}
}
}
// 从 1 出发逐层推进,长度已被固定为 D,每层只在"能走完剩余最短路"的
// 出边里取最小颜色,就得到字典序最小的颜色序列;每个点只入层一次,
// 因此所有层的出边扫描量合计 O(n + m)
void build_answer(int n, int& out_len) {
int D = dist_to_n[1]; // 最短路长度(边数)
out_len = 0;
for (int i = 1; i <= n; i++) in_layer[i] = 0;
int cur_len = 0;
cur_layer[cur_len++] = 1; // 第 0 层的唯一节点
in_layer[1] = 1;
while (out_len < D) {
int target = D - out_len - 1; // 下一层节点必须满足 dist_to_n == target
int cmin = INT_MAX;
for (int i = 0; i < cur_len; i++) {
int u = cur_layer[i];
for (int e = head[u]; e != 0; e = edge[e].nxt) {
int v = edge[e].to;
if (dist_to_n[v] == target && edge[e].color < cmin) cmin = edge[e].color;
}
}
out_seq[out_len++] = cmin; // 这一位的颜色确定为 cmin
int nxt_len = 0;
for (int i = 0; i < cur_len; i++) {
int u = cur_layer[i];
for (int e = head[u]; e != 0; e = edge[e].nxt) {
int v = edge[e].to;
// 只保留"走最小颜色且 dist 恰好少 1"的点,它们一定能续走到 n
if (dist_to_n[v] == target && edge[e].color == cmin && !in_layer[v]) {
in_layer[v] = 1;
nxt_layer[nxt_len++] = v;
}
}
}
for (int i = 0; i < nxt_len; i++) cur_layer[i] = nxt_layer[i];
cur_len = nxt_len;
}
}
int main() {
ll T; // 数据组数
if (scanf("%lld", &T) != 1) return 0;
while (T--) {
int n, m;
scanf("%d %d", &n, &m);
edge_cnt = 0; // 多组数据:邻接表按组重建
for (int i = 1; i <= n; i++) head[i] = 0;
for (int i = 0; i < m; i++) {
int a, b, c;
scanf("%d %d %d", &a, &b, &c);
if (a == b) continue; // 自环不可能落在最短路上,直接丢掉
add_edge(a, b, c);
}
bfs_reverse(n);
if (dist_to_n[1] == -1) { // 题面未定义 1 到 n 不连通的情况,约定输出 0 与空行
printf("0\n\n");
continue;
}
int out_len;
build_answer(n, out_len);
printf("%d\n", out_len);
for (int i = 0; i < out_len; i++)
printf("%d%c", out_seq[i], i + 1 == out_len ? '\n' : ' ');
}
return 0;
}两份代码都是"反向 BFS + 分层贪心":main.py 用 deque 与生成器表达式把候选取最小写成一行,
main.cpp 用链式前向星与手写队列,两个数组 cur_layer / nxt_layer 交替充当相邻层,
全程没有 vector 与 set,配合 int 邻接表把峰值内存压在 10 MB 以内。
复杂度
- 时间:反向 BFS 每个点、每条边各访问一次,
;分层贪心每个点只入层一次, 出边合计也只扫一遍, 。多组数据按 计。 实测最大数据( ,每组 、 )C++ 约 0.27 s(限时 1000 ms)。 - 空间:邻接表存
条半边, ,C++ 实测峰值约 8.4 MB(限时 64 MB)。 - Python 侧风险:
main.py只依赖标准库,deque+ 生成器最坏情况约为 C++ 的 20–40 倍常数, 在真实数据problem10.in(10 组满规模)上实测约 1.9 s,超过 1 s 限时。 按oj-python-style的约定,Python 短解法允许 TLE,但算法与 C++ 同阶; 正式提交请用main.cpp。
总结
- 两个目标要分两步拆:颜色序列的长度等于路径边数,所以"长度最短"是硬约束,
必须先用一次 BFS 把它算出来并钉死,之后字典序才有意义。用反向 BFS
(从
出发)而不是正向 BFS,是因为决策时需要的是"到终点还有多远"。 - 分层贪心的合法性来自"同一层条件齐平":
把所有候选点 压在同一个前缀长度、同一个剩余距离上,逐位取最小颜色才不会互相干扰; 这一条同时排除了死路——满足等式的点一定能续走到 。 - 每个点只入层一次是复杂度的关键:层号由
唯一决定,重复入层是纯浪费。 加上 in_layer标记后,总扫描量与层数无关,稳定。 - 平行边必须逐条保留:同一对点之间的不同颜色边是独立的候选转移,
样例里
1 3这个答案正是靠"第二条颜色更小的平行边"才取到的。
图示解析
下图画出样例的分层结构:三个子图是按
flowchart LR
subgraph L0["k=0, dist=2"]
A["1"]
end
subgraph L1["k=1, dist=1"]
B["2"]
C["3"]
end
subgraph L2["k=2, dist=0"]
D["4"]
end
A -.->|1 未选中| B
A -.->|2 未选中| C
A -->|1 选中| C
B -.->|4 未选中| D
C -->|3 选中| D
从图上看三件事:节点