最优路径

GitHub跳转原题关系图返回列表

先从 n 反向 BFS 求各点到 n 的最短边数,再从 1 出发按层在出边里取最小颜色并只保留走完剩余最短路的点,得到字典序最小的颜色序列。

OJ: roj

题目 ID: 1688

难度:提高

标签:图论BFS最短路贪心字典序python

创建: 2026-10-07 15:30

更新: 2026-10-07 15:30

形式化题目

给定无向图 G=(V,E)G = (V, E),∣V∣=n|V| = n、∣E∣=m|E| = m,每条边 ee 有两个属性:长度恒为 11, 颜色 cec_e(1⩽ce⩽1091 \leqslant c_e \leqslant 10^9)。一条从 11 到 nn 的路径

P=(v0=1,v1,…,vk=n)P = (v_0 = 1, v_1, \dots, v_k = n)

对应颜色序列 C(P)=(cv0v1,…,cvk−1vk)C(P) = (c_{v_0 v_1}, \dots, c_{v_{k-1} v_k})。要求在所有从 11 到 nn 的路径中:

  1. 先最小化边数 kk;
  2. 在边数取到最小值 DD 的前提下,最小化颜色序列的字典序。

输出 DD 与这个字典序最小的颜色序列。图不保证无重边、无自环;多组数据。

这里出现了两个目标,并且是字典序意义下的两级目标:先把可行解集缩小到"长度 = DD"这一层, 再在这一层里比字典序。所以问题的本质是:

min⁡P: ∣P∣=DC(P)(按字典序),D=dist(1,n).\min_{P:\ |P| = D} C(P) \quad \text{(按字典序)},\qquad D = \text{dist}(1, n).

正解

思路

第一步:把"长度"这个自由度消掉。 一条路径的颜色序列长度等于它的边数,所以字典序比较 只发生在长度相同的两条路径之间——长度一旦不同,短的直接胜出。于是要先知道 DD。 从 nn 出发做一次反向 BFS(边长全为 11,BFS 首次到达即最短),就得到

dist[v]=v 到 n 的最短边数,\mathrm{dist}[v] = v \text{ 到 } n \text{ 的最短边数},

D=dist[1]D = \mathrm{dist}[1]。反向 BFS 的好处是一次就拿到所有点离终点的距离,而正向 BFS 只能给出离起点的距离,对"能不能走完剩下这段路"没有信息。

第二步:字典序就是"逐位贪心"。 长度已被钉死为 DD,剩下的是一个逐位决策的问题: 第 11 位颜色、第 22 位颜色……每一位都希望尽量小。设走完前 kk 位后停在节点 uu, 则剩余 D−kD - k 位必须由一条 u→nu \to n 的、长度为 D−kD - k 的路径提供,也就是要求

dist[u]=D−k.\mathrm{dist}[u] = D - k .

这条等式就是全部约束:它保证"位号 = 剩余距离",任何满足它的节点都一定能续走到 nn (沿 dist\mathrm{dist} 每次减 11 的边一直走即可),因此不会走进死路。反过来,若不满足, 要么走不到 nn,要么会超出 DD 位。

于是算法是:

  • 维护当前层 cur:所有可以作为"某条最优路径第 kk 个终点"的节点,它们都满足 dist=D−k\mathrm{dist} = D - k;
  • 枚举 cur 中所有指向 dist=D−k−1\mathrm{dist} = D - k - 1 的节点的出边,取其中最小颜色 cmin, 它就是答案的第 k+1k+1 位(因为比它小的颜色在这一位没有任何可行边,而它自己一定可行);
  • 下一层 = 所有"颜色恰为 cmin、dist\mathrm{dist} 恰为 D−k−1D - k - 1"的出边终点, 并且每个点只入层一次(in_layer 标记)。

第三步:为什么第二位贪心不会破坏第一位? 这是分层贪心最常见的疑问。答案是: 判定"第 k+1k+1 位能不能取到 cc"只依赖 dist\mathrm{dist} 与边颜色,与前缀具体是怎么走过来的无关。 只要当前节点 uu 满足 dist[u]=D−k\mathrm{dist}[u] = D - k,那么"从 uu 出发,前一位取 cc"就等价于 “存在一条从 uu 到 nn 的长度恰为 D−kD-k 的路径,且第一条边颜色为 cc”——是个只与 uu 有关的谓词。 所以前缀长度相同、位数相同时,字典序比较逐位独立,可以在第 k+1k+1 位独立取最小值。 而所有候选节点都保证了前缀长度 =k= k、剩余距离 =D−k= D - k,条件齐平,逐位贪心合法。

为什么每个点只入层一次就够? 层号 kk 由 dist\mathrm{dist} 唯一确定(k=D−dist[v]k = D - \mathrm{dist}[v]), 一个点不可能出现在两个不同层里;同一层里重复入队也只会让出边被重复扫。加 in_layer 标记后, 每个点最多被扫出边一次,总扫描量 O(n+m)O(n + m),与层数无关。

用题目样例走一遍(n=4n = 4,66 条边,其中 11–33 有两条颜色分别为 22 和 11 的平行边):

层 kk 当前层节点 dist\mathrm{dist} 应为 候选出边(节点, 颜色) cmin 下一层
0 {1}\{1\} 1 (2,1)(2,1), (3,2)(3,2), (3,1)(3,1) 1 {2,3}\{2, 3\}
1 {2,3}\{2, 3\} 0 (2→4,4)(2{\to}4, 4), (3→4,3)(3{\to}4, 3) 3 {4}\{4\}

dist[4]=0\mathrm{dist}[4] = 0、dist[2]=dist[3]=1\mathrm{dist}[2] = \mathrm{dist}[3] = 1、dist[1]=2\mathrm{dist}[1] = 2, 所以 D=2D = 2;答案是 1 3,与样例一致。

注意第 0 层的候选里 (3,1)(3,1) 这条边:节点 33 是通过 11–33 的第二条平行边(颜色 11) 进入第 1 层的,而不是通过颜色为 22 的那条。第 1 层于是在 {2,3}\{2, 3\} 上取 min⁡(4,3)=3\min(4, 3) = 3,得 1 3;如果只把节点 33 按第一条扫到的边(颜色 22)入层, 就会以为第 0 位只能是 22,答案错成 2 3。这说明"同一对点之间的不同颜色边各自独立成一次转移", 平行边必须全部保留。

关于不连通: 题面没有定义 11 无法到达 nn 时输出什么,本仓库约定输出 0 与一个空行。 十组官方数据都不触发这个分支(std.cpp 与本解在此约定上一致)。

代码

Python 版:

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++ 版(同一算法):

cpp
/**
 * 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 每个点、每条边各访问一次,O(n+m)O(n + m);分层贪心每个点只入层一次, 出边合计也只扫一遍,O(n+m)O(n + m)。多组数据按 ∑(ni+mi)\sum (n_i + m_i) 计。 实测最大数据(T=10T = 10,每组 n=105n = 10^5、m=2×105m = 2 \times 10^5)C++ 约 0.27 s(限时 1000 ms)。
  • 空间:邻接表存 2m2m 条半边,O(n+m)O(n + m),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 (从 nn 出发)而不是正向 BFS,是因为决策时需要的是"到终点还有多远"。
  • 分层贪心的合法性来自"同一层条件齐平":dist[v]=D−k\mathrm{dist}[v] = D - k 把所有候选点 压在同一个前缀长度、同一个剩余距离上,逐位取最小颜色才不会互相干扰; 这一条同时排除了死路——满足等式的点一定能续走到 nn。
  • 每个点只入层一次是复杂度的关键:层号由 dist\mathrm{dist} 唯一决定,重复入层是纯浪费。 加上 in_layer 标记后,总扫描量与层数无关,稳定 O(n+m)O(n + m)。
  • 平行边必须逐条保留:同一对点之间的不同颜色边是独立的候选转移, 样例里 1 3 这个答案正是靠"第二条颜色更小的平行边"才取到的。

图示解析

下图画出样例的分层结构:三个子图是按 dist\mathrm{dist} 分的层(层内节点到 nn 的最短距离相同), 实线箭头是最终答案 1→3→41 \to 3 \to 4 用到的两条边,虚线箭头是候选但未选中的边。

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

从图上看三件事:节点 11 到 44 只有两条可能的边(1→2→41\to 2\to 4 与 1→3→41\to 3\to 4), 所以 D=2D = 2,颜色序列只有两位。第 1 位由 11 的三条出边里最小的颜色决定,是 11; 而 11 到 33 之间有两条平行边,一条颜色 22、一条颜色 11,只要有一条颜色为 11, 节点 33 就能进入第 1 层——这正是答案不是 2 32\,3 的原因。第 2 位在 {2,3}\{2, 3\} 上竞争, 2→42 \to 4 的颜色 44 输给 3→43 \to 4 的颜色 33,于是最终序列为 1 31\,3。