次短路计数

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

把每个点拆成最短路与严格次短路两个状态跑 Dijkstra,最短路退位时条数一起搬走,答案取最短路条数加次短路恰好多 1 的条数。

OJ: roj

题目 ID: 1716

难度:提高

标签:图论最短路Dijkstra计数python

创建: 2026-10-07 17:58

更新: 2026-10-07 17:58

形式化题目

给定有向图 G=(V,E)G=(V,E)、每条边 e=(x,y)e=(x,y) 的权 we⩾1w_e \geqslant 1(无自环)以及两个不同的点 s,ts, t,且保证 ss 到 tt 至少存在一条路线。记一条 s→ts \to t 的路线为一个边序列 P=(e1,e2,…,ek)P = (e_1, e_2, \dots, e_k)(允许重复经过点),其长度 ℓ(P)=∑iwei\ell(P) = \sum_{i} w_{e_i}。 两条路线不同,当且仅当存在一条边属于其中一条而不属于另一条,即按边的多重集判定:

P≠Q  ⟺  ∃ e:(e∈P∧e∉Q)∨(e∈Q∧e∉P). P \neq Q \iff \exists\, e: \bigl(e \in P \wedge e \notin Q\bigr) \vee \bigl(e \in Q \wedge e \notin P\bigr).

注意 x,y,wx,y,w 完全相同的两条平行边是两条不同的边,因此它们是不同的路线。记 d0=min⁡Pℓ(P)d_0 = \min_{P} \ell(P),要求输出

∣{ P:ℓ(P)=d0 }∣  +  ∣{ P:ℓ(P)=d0+1 }∣. \Bigl|\{\,P : \ell(P) = d_0\,\}\Bigr| \;+\; \Bigl|\{\,P : \ell(P) = d_0 + 1\,\}\Bigr| .

多组数据,每组一行整数;保证答案不超过 10910^9。

正解

思路

朴素做法。 枚举所有 s→ts \to t 的路线并统计长度分布。路线数可以指数级爆炸, 在 n⩽1000n \leqslant 1000、m⩽10000m \leqslant 10000 上完全不可行。

该记什么。 题目要的不是一条路线,而是"长度恰好落在 d0d_0 与 d0+1d_0+1 上的路线条数"。 这提示把最短路计数推广一层:对每个点 vv 同时维护

  • dist[v][0]\mathrm{dist}[v][0]:s→vs \to v 的最短距离,cnt[v][0]\mathrm{cnt}[v][0] 为达到它的路线条数;
  • dist[v][1]\mathrm{dist}[v][1]:s→vs \to v 的严格次短距离(dist[v][1]>dist[v][0]\mathrm{dist}[v][1] > \mathrm{dist}[v][0]), cnt[v][1]\mathrm{cnt}[v][1] 为达到它的路线条数。

于是所求

ans=cnt[t][0]+{cnt[t][1],dist[t][1]=dist[t][0]+1,0,否则. \text{ans} = \mathrm{cnt}[t][0] + \begin{cases} \mathrm{cnt}[t][1], & \mathrm{dist}[t][1] = \mathrm{dist}[t][0] + 1,\\ 0, & \text{否则}. \end{cases}

为什么可以在"状态"上跑 Dijkstra。 把每个点 vv 拆成两个状态 (v,0)(v,0) 与 (v,1)(v,1), 在状态图上跑最短路。堆按距离升序弹出,取出状态 (u,k)(u,k) 时它的 dist\mathrm{dist} 与 cnt\mathrm{cnt} 都已定型,再用它去松弛所有出边 u→vu \to v,候选值 nd=dist[u][k]+wnd = \mathrm{dist}[u][k] + w,分四类:

条件 动作
nd<dist[v][0]nd < \mathrm{dist}[v][0] 老的最短路退位成次短路(dist[v][1]←dist[v][0]\mathrm{dist}[v][1] \leftarrow \mathrm{dist}[v][0]、cnt[v][1]←cnt[v][0]\mathrm{cnt}[v][1] \leftarrow \mathrm{cnt}[v][0]);dist[v][0]←nd\mathrm{dist}[v][0] \leftarrow nd、cnt[v][0]←cnt[u][k]\mathrm{cnt}[v][0] \leftarrow \mathrm{cnt}[u][k]
nd=dist[v][0]nd = \mathrm{dist}[v][0] cnt[v][0]+=cnt[u][k]\mathrm{cnt}[v][0] \mathrel{+}= \mathrm{cnt}[u][k]
nd<dist[v][1]nd < \mathrm{dist}[v][1] dist[v][1]←nd\mathrm{dist}[v][1] \leftarrow nd、cnt[v][1]←cnt[u][k]\mathrm{cnt}[v][1] \leftarrow \mathrm{cnt}[u][k]
nd=dist[v][1]nd = \mathrm{dist}[v][1] cnt[v][1]+=cnt[u][k]\mathrm{cnt}[v][1] \mathrel{+}= \mathrm{cnt}[u][k]

两个需要论证的点。

  1. 退位时条数可以整批搬走。 设老值为 dist[v][0]=D\mathrm{dist}[v][0] = D、条数 CC, 而这些条数确实把 nd<Dnd < D 顶了下去。此后任何长度恰为 DD 的 s→vs \to v 路线, 都不再满足 nd′=dist[v][0]nd' = \mathrm{dist}[v][0](那时 dist[v][0]=nd<D\mathrm{dist}[v][0] = nd < D), 而满足 nd′=dist[v][1]=Dnd' = \mathrm{dist}[v][1] = D,会在第四类里被重新累加。 所以搬走 CC 之后不会重复计数,也不会漏:DD 层的新贡献照旧进 cnt[v][1]\mathrm{cnt}[v][1]。

  2. 状态出堆后不会被再次累加。 设 (v,k)(v,k) 出堆后又被某个状态 (u′,k′)(u',k') 贡献, 则要求 dist[u′][k′]+w=dist[v][k]\mathrm{dist}[u'][k'] + w = \mathrm{dist}[v][k] 而 (u′,k′)(u',k') 出堆更晚。 但 w⩾1w \geqslant 1 给出 dist[u′][k′]<dist[v][k]\mathrm{dist}[u'][k'] < \mathrm{dist}[v][k], 距离更小的状态必然先出堆,矛盾。因此长度为 dist[v][k]\mathrm{dist}[v][k] 的路线,其前驱状态的 距离严格更小、一定先被确定,cnt[v][k]\mathrm{cnt}[v][k] 在 (v,k)(v,k) 出堆时已经收齐。 ——这也正是权值必须 ⩾1\geqslant 1 的地方;若允许 00 权边或负权边, 同一状态会被后到的等长/更短路线二次贡献,本做法给出的计数就不可靠了。

有环会不会多算? 因为无自环且每条边 w⩾1w \geqslant 1,任何环至少含 22 条边、权至少为 22。 于是任何满足 ℓ(P)⩽d0+1\ell(P) \leqslant d_0 + 1 的 s→ts \to t 路线必是简单路径:若它重复经过某个点, 就含一个权 ⩾2\geqslant 2 的环,去掉环得到长度 ⩽d0−1\leqslant d_0 - 1 的路线,矛盾。 所以本题"路线"虽然允许重复经过点,却与"简单路径计数"等价,图里有无环都不影响答案语义, 只有长度 ⩽d0+1\leqslant d_0+1 的那些路径会真正参与计数。

平行边。 邻接表里平行边各占一项,松弛时各自独立触发一次"nd=dist[v][k]nd = \mathrm{dist}[v][k]", 自然按题面的"边集不同"口径分开计数。样例 2 的答案 22 正来自两条 5→725 \xrightarrow{7} 2 平行边:4→5→2→3→14 \to 5 \to 2 \to 3 \to 1 是最短路(2+7+1+10=202+7+1+10 = 20), 这两条等权平行边给出两条不同的最短路路线,故 cnt[1][0]=2\mathrm{cnt}[1][0] = 2。

实现细节。

  • 每个状态只被"确定"一次,出堆时若 d != dist[u][k] 就丢弃(陈旧状态)。
  • 也可以额外开一个 done[u][k] 布尔数组显式去重,效果相同(本题 main.cpp 就是这么写的)。
  • TT 组数据共用数组,每组开头必须把边表、dist、cnt、done 全部重置。
  • n⩽1000n \leqslant 1000、m⩽10000m \leqslant 10000、TT 可达 1010,用链式前向星而非 vector 邻接表 可以少一次清空。

样例逐组核算。 把程序内部的两个状态打出来看:

组 s→ts \to t dist[t][0]/cnt[t][0]\mathrm{dist}[t][0] / \mathrm{cnt}[t][0] dist[t][1]/cnt[t][1]\mathrm{dist}[t][1] / \mathrm{cnt}[t][1] 答案 说明
1 1→51 \to 5 6 / 26\,/\,2 7 / 17\,/\,1 2+1=32 + 1 = 3 两条最短路 1→3→51\to3\to5(2+42+4)与 1→2→51\to2\to5(3+33+3);次短路 1→3→4→51\to3\to4\to5(2+2+3=72+2+3=7)恰好多 11,计入
2 4→14 \to 1 20 / 220\,/\,2 22 / 222\,/\,2 2+0=22 + 0 = 2 两条 5→725 \xrightarrow{7} 2 平行边贡献最短路 22 条;22≠2122 \ne 21,次短路不计

两组输出与题面样例逐字符一致(实际输出 3 / 2)。

代码

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 11:05
# update_at: 2026-10-07 11:05

import sys
from heapq import heappop, heappush

INF = 1 << 60  # 距离哨兵:任何真实路径长度都远小于它

# 类型别名(Python 3.12+ 的 type 语句),相当于 C++ 的 using / typedef
type Graph = list[list[tuple[int, int]]]  # 邻接表 g[u] = [(v, w), ...],重边各占一项


def count_routes(g: Graph, s: int, t: int) -> int:
    """返回 s->t 的「最短路条数 + 次短路恰好多 1 时的次短路条数」。

    每个点拆成两个状态 (u, k):k=0 最短路、k=1 严格次短路,在状态上跑 Dijkstra。
    边权 >= 1,所以长度为 dist[v][k] 的路线其前驱状态距离严格更小、必先出堆,
    于是 (v,k) 出堆时它的条数已经收齐,出堆后用不着再回头累加。
    """
    n = len(g) - 1  # g 用 1..n 编号,0 号位空占
    dist = [[INF, INF] for _ in range(n + 1)]
    cnt = [[0, 0] for _ in range(n + 1)]  # 与 dist 逐格对应的路线条数
    dist[s][0], cnt[s][0] = 0, 1
    heap = [(0, s, 0)]

    while heap:
        d, u, k = heappop(heap)
        if d != dist[u][k]:
            continue  # 陈旧状态:同一状态已被更短的距离取代
        for v, w in g[u]:
            nd = d + w
            if nd < dist[v][0]:
                if dist[v][0] < dist[v][1]:
                    # 老的最短路退位成次短路,条数一起搬走;此后同长度的贡献
                    # 都会落进下面 nd == dist[v][1] 那一支继续累加
                    dist[v][1], cnt[v][1] = dist[v][0], cnt[v][0]
                    heappush(heap, (dist[v][1], v, 1))
                dist[v][0], cnt[v][0] = nd, cnt[u][k]
                heappush(heap, (nd, v, 0))
            elif nd == dist[v][0]:
                cnt[v][0] += cnt[u][k]  # 另一条等长路线
            elif nd < dist[v][1]:
                dist[v][1], cnt[v][1] = nd, cnt[u][k]
                heappush(heap, (nd, v, 1))
            elif nd == dist[v][1]:
                cnt[v][1] += cnt[u][k]

    if dist[t][1] == dist[t][0] + 1:
        return cnt[t][0] + cnt[t][1]
    return cnt[t][0]


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)
        g: Graph = [[] for _ in range(n + 1)]
        for _ in range(m):
            x, y, w = next(data), next(data), next(data)
            g[x].append((y, w))  # 平行边各占一项,天然按「边集不同」区分路线
        s, t = next(data), next(data)
        out.append(str(count_routes(g, s, t)))

    print('\n'.join(out))


if __name__ == "__main__":
    solve()

C++ 版(同一算法):

cpp
// 1716 次短路计数
// ---------------------------------------------------------------------------
// 题意:给定有向带权图与源点 s、汇点 t,求「长度 = 最短路长度」的 s->t 路线条数,
//       再加上「长度 = 最短路长度 + 1」的 s->t 路线条数(不存在则不加)。
//       两条路线不同 <=> 存在至少一条边属于其中一条而不属于另一条(边集不同),
//       因此重边各自独立计一次。
//
// 做法:把每个点拆成两个状态 (u,k),k=0 表示「到 u 的最短路」,k=1 表示
//       「到 u 的严格次短路」。在 (u,k) 上跑 Dijkstra:
//         - 堆按距离升序弹出,每个状态只被确定一次,确定性后再暴力松弛出边;
//         - 设边 u->v 权 w,松弛值 nd = dist[u][k] + w,分四类处理:
//             nd <  dist[v][0]  -> 原 dist[v][0] 退位成 dist[v][1](计数一并搬过去),
//                                  nd 顶替成新的 dist[v][0],计数置为 cnt[u][k];
//             nd == dist[v][0]  -> cnt[v][0] += cnt[u][k](同长度路径累加);
//             nd <  dist[v][1]  -> 更新 dist[v][1] 并置计数为 cnt[u][k];
//             nd == dist[v][1]  -> cnt[v][1] += cnt[u][k]。
//       退位时「计数一并搬走」是正确的:此后所有长度等于旧 dist[v][0] 的路径
//       都会落进 nd == dist[v][1] 这一支,被继续累加到 cnt[v][1] 上。
//
//       关于计数何时定型:边权 >= 1,所以长度等于 dist[v][k] 的路径,其前驱状态
//       的距离严格小于 dist[v][k],一定先于 (v,k) 被弹出;于是 (v,k) 出堆时
//       cnt[v][k] 已收齐。同理,状态出堆后再被累加是不可能的(那将要求 w <= 0)。
//
//       答案 = cnt[t][0] + (dist[t][1] == dist[t][0] + 1 ? cnt[t][1] : 0)。
//
// 复杂度:O(T * (n + m) log n) 时间(每个点两个状态、每条边被松弛至多两次),
//         堆内元素 O(n),其余数组 O(n),空间 O(n + m)。
// 数据规模:2 <= n <= 1000,1 <= m <= 10000,1 <= w <= 1000,答案 <= 1e9。
// ---------------------------------------------------------------------------
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 1005;      // 点数上界
const int MAXM = 10005;     // 边数上界
const int INF = 0x3f3f3f3f; // 无穷大(两条最短路相加不会溢出)

// 链式前向星存边:重边各自占一条边,天然满足「边集不同即路线不同」
int head[MAXN], nxt[MAXM], to[MAXM], wt[MAXM], ecnt;

int n, m, s, t;
int dist[MAXN][2];   // dist[u][0] 最短路;dist[u][1] 严格次短路
ll cnt[MAXN][2];     // 对应条数
bool done[MAXN][2];  // 该状态是否已被最终确定

// 堆中元素:状态 (u, k) 及其距离 d
struct State {
    int d, u, k;
    bool operator<(const State &o) const { return d > o.d; } // 小根堆
};

// 加一条有向边 x -> y,权 w
void addEdge(int x, int y, int w) {
    ++ecnt;
    to[ecnt] = y;
    wt[ecnt] = w;
    nxt[ecnt] = head[x];
    head[x] = ecnt;
}

// 初始化一组数据
void init() {
    ecnt = 0;
    for (int i = 1; i <= n; ++i) {
        head[i] = 0;
        dist[i][0] = dist[i][1] = INF;
        cnt[i][0] = cnt[i][1] = 0;
        done[i][0] = done[i][1] = false;
    }
}

// 用状态 (u, k) 的确定值去松弛 v,nd 为候选距离
void relax(int v, int nd, int u, int k, priority_queue<State> &pq) {
    if (nd < dist[v][0]) {
        // 老的最短路被顶下去,成为次短路(计数一起搬走)
        if (dist[v][0] < dist[v][1]) {
            dist[v][1] = dist[v][0];
            cnt[v][1] = cnt[v][0];
            pq.push(State{dist[v][1], v, 1});
        }
        dist[v][0] = nd;
        cnt[v][0] = cnt[u][k];
        pq.push(State{nd, v, 0});
    } else if (nd == dist[v][0]) {
        cnt[v][0] += cnt[u][k];
    } else if (nd < dist[v][1]) {
        dist[v][1] = nd;
        cnt[v][1] = cnt[u][k];
        pq.push(State{nd, v, 1});
    } else if (nd == dist[v][1]) {
        cnt[v][1] += cnt[u][k];
    }
}

// 单组数据的求解(调用前需已 init() 并读入全部边)
ll solve() {
    priority_queue<State> pq;
    dist[s][0] = 0;
    cnt[s][0] = 1;
    pq.push(State{0, s, 0});

    while (!pq.empty()) {
        State cur = pq.top();
        pq.pop();
        int u = cur.u, d = cur.d, k = cur.k;
        if (done[u][k] || d != dist[u][k]) continue; // 已经确定过 / 陈旧状态
        done[u][k] = true;
        for (int e = head[u]; e; e = nxt[e]) {
            int v = to[e];
            relax(v, d + wt[e], u, k, pq);
        }
    }

    ll ans = cnt[t][0];
    // 只额外统计「恰好比最短路多 1 个单位」的那一层
    if (dist[t][1] == dist[t][0] + 1) ans += cnt[t][1];
    return ans;
}

int main() {
    int T;
    if (scanf("%d", &T) != 1) return 0;
    while (T--) {
        if (scanf("%d %d", &n, &m) != 2) break;
        init(); // 先清空上一组数据的边表与距离,再向其中加边
        for (int i = 0; i < m; ++i) {
            int x, y, w;
            scanf("%d %d %d", &x, &y, &w);
            addEdge(x, y, w);
        }
        scanf("%d %d", &s, &t);
        printf("%lld\n", solve());
    }
    return 0;
}

复杂度

  • 时间:每个点两个状态、每条边被松弛至多两次。堆中每个状态最多因距离被更新而入堆 若干次,但只被确定一次,故为 O((n+m)log⁡n)O\bigl((n + m) \log n\bigr) 每组数据, TT 组总计 O(T (n+m)log⁡n)O\bigl(T\, (n + m) \log n\bigr)。
  • 空间:dist / cnt / done 各 O(n)O(n),链式前向星 O(m)O(m),堆 O(n)O(n), 合计 O(n+m)O(n + m);按 n⩽1000n \leqslant 1000、m⩽10000m \leqslant 10000 计约几百 KB, 远低于 64 MB 限制。
  • 与 C++ 解法的关系:main.py 是同一算法的 Python 版本,用 heapq 与邻接表, 复杂度同阶。实测 10 个测试点全部在 0.05 s 内跑完,Python 侧无 TLE 风险。

总结

  • 计数问题的第一反应是"把答案改造成可加的量":本题不是求一条最短路,而是求两个 长度层上的条数,于是最短路计数被原样推广到"最近的两层"。
  • 点拆成状态是最短路计数的通用外壳:(u,k)(u,k) 的 kk 只有 0/10/1 两档,但它让 “次短路"从"需要额外讨论的东西"变成"状态图上的一个普通点”,松弛逻辑仍是 Dijkstra 那一套。
  • 退位要连计数一起搬走:dist[v][0]→dist[v][1]\mathrm{dist}[v][0] \to \mathrm{dist}[v][1] 时若只搬距离不搬条数, 就会漏掉全部老最短路的贡献;搬走之后同长度的新贡献又会自动落进 cnt[v][1]\mathrm{cnt}[v][1],所以既不重也不漏。
  • ans\mathrm{ans} 只在次短路恰好多 11 时才加:题面要的是"恰好多一个单位距离"的路线, dist[t][1]>dist[t][0]+1\mathrm{dist}[t][1] > \mathrm{dist}[t][0] + 1 时 cnt[t][1]\mathrm{cnt}[t][1] 里的路线一律不计。
  • 权值 ⩾1\geqslant 1 是算法正确性的前提(保证等长路线的前驱状态先出堆)。 本题数据满足该条件;若换成 00 权边,需改用"距离分层 + 拓扑序"或 BFS 式惰性计数。
  • 重边必须各占一条边:题面的"路线不同"按边集判定,平行边是不同路线, 样例 2 的答案 22 就建立在两条 5→25 \to 2 权为 77 的平行边上。

附注:素材与数据来源

  • 本题题面与 POJ 3463 Sightseeing 的输入输出样例逐字一致,可视为同一题的收录版本; std.cpp 的头部注释也记录了这一点,并说明其算法是"按公开题解思路自行重写"而非逐行复制。
  • 本目录的 std.cpp 已实际编译(g++-16 -O2)并在随仓的 10 个测试点、以及题面样例上 与期望输出逐点比对,结果全部一致,故其算法(状态拆点 + Dijkstra 计数)与题面自洽, 本文的 main.cpp / main.py 按同一算法独立重写。
  • 素材源目录同时带有数据生成脚本 data.py,说明 data/ 是自造的(10 组, 分层覆盖边界、小规模、n=1000/m=10000n=1000 / m=10000 顶格、大答案 967458816967458816 与 430467210430467210 等分支), 并非官方原始数据。因此"本地全部测试点通过"不等于官方 AC, 题面本身也可能与官方原题存在偏差(例如是否要求输出次短路条数之和而非合并为一个整数)。 本文按题面字面口径实现:每组只输出一个整数。