正则表达式

形式化题目

给定一张 $n$ 个点、 $m$ 条边的带权有向图，边 $u \to v$ 的权值为 $w \geqslant 0$ 。规则是：

若 $u$ 能到达 $v$ ，且 $v$ 也能到达 $u$ （即 $u$ 、 $v$ 互相可达），则 $u$ 与 $v$ 之间的传输耗时为 $0$ 。

求点 $1$ 到点 $n$ 的最小传输耗时。重边、自环都可能出现。

关键是把“ $u$ 、 $v$ 互相可达”认成一种等价关系：它把点集划分成若干组，组内任意两点耗时都是 $0$ ，组间才按原边权计费。这种等价关系在图论里有一个现成的名字——强连通分量。所以本题的实质是：

把每个强连通分量缩成一个点（分量内部边权视为 $0$ ），在缩点后的图上求最短路。

暴力解法

思路

先不引入任何图论概念，只把题面这句话逐字翻译成代码。判断“ $u$ 能不能到 $v$ ”最直白的办法是 Floyd 传递闭包：

用 reach[i][j] 表示 $i$ 能否走到 $j$ ，初始时只有边和 reach[i][i] = true；
跑一遍 Floyd 闭包，得到所有可达关系；
对每个点对 $(i,j)$ ：若 reach[i][j] && reach[j][i]，说明两者互相可达，属于同一局域网，把 dist[i][j] 置 $0$ ；否则保留原边权；
再跑一遍 Floyd，在带上这些 $0$ 权边的图上求 $1$ 到 $n$ 的最短路。

这版代码就是题意的直接翻译，没有任何技巧，因此它是对的——它就是“互相可达则耗时 $0$ ”这句话本身。代价是完全的 $O(n^3)$ ，只能过 $40\%$ 的数据。

顺带一提，这也是检验理解是否正确的试金石。如果只把“存在 $A\to B$ 且存在 $B\to A$ ”读成“直接互相有边”，第 3 步就会改成“只对存在直接反向边的点对置 $0$ ”，那个写法在本文章的样例 2 上会输出 $9$ 而不是 $3$ （原因见“正解”一节）。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80/**
 * 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-03 10:41
 * update_at: 2026-10-03 10:45
 */
// brute.cpp：洛谷 P2169 的最朴素暴力解，用于理解题意并和 main.cpp 对拍。
//
// 暴力思路完全不碰“强连通分量”这个概念，只做最直白的翻译：
//   1. 用 Floyd 求传递闭包 reach[i][j]，即“i 能不能走到 j”；
//   2. 若 reach[i][j] 和 reach[j][i] 同时成立，说明 i、j 处于同一局域网，
//      它们之间的传输时间为 0，于是把 dist[i][j] 置 0；
//   3. 再用 Floyd 在带 0 权的图上求 1 到 n 的最短路。
//
// 复杂度 O(n^3)，只能用于小数据，但每一步都是对题意的直接翻译，
// 所以它是对的：它就是“局域网内部耗时 0”这句话本身。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn = 305;          // 暴力只用在小数据上
const ll INF = 1e18;

int n, m;
ll dist[maxn][maxn];           // dist[i][j]：i 到 j 的当前最短距离
bool reach[maxn][maxn];        // reach[i][j]：i 能否到达 j

int main() {
    scanf("%d %d", &n, &m);

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            dist[i][j] = INF;
            reach[i][j] = false;
        }
        dist[i][i] = 0;
        reach[i][i] = true;     // 自己一定能到自己
    }

    for (int i = 1; i <= m; i++) {
        int u, v, c;
        scanf("%d %d %d", &u, &v, &c);
        if (c < dist[u][v]) dist[u][v] = c;   // 重边保留最小的一条
        reach[u][v] = true;
    }

    // 第一步：Floyd 求传递闭包
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            if (!reach[i][k]) continue;
            for (int j = 1; j <= n; j++) {
                if (reach[k][j]) reach[i][j] = true;
            }
        }
    }

    // 第二步：互相可达 => 同一局域网 => 传输时间 0
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (reach[i][j] && reach[j][i]) dist[i][j] = 0;
        }
    }

    // 第三步：Floyd 求最短路
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            if (dist[i][k] >= INF) continue;
            for (int j = 1; j <= n; j++) {
                if (dist[k][j] >= INF) continue;
                if (dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }

    printf("%lld\n", dist[1][n]);
    return 0;
}

复杂度

时间复杂度：两遍 Floyd， $O(n^3)$ ；
空间复杂度： $O(n^2)$ 。

瓶颈

瓶颈在“判断任意两点是否互相可达”这件事本身。它是一个全源可达性问题，朴素做法对每个点对都要重新判断，于是花了 $O(n^3)$ 。

但换个角度想：题目其实并不关心“点 $i$ 到点 $j$ 具体怎么走”，它只关心“哪些点两两互相可达”，也就是只要把这个等价关系分好组就行。用一个 $O(n^3)$ 的算法去算一个只需要“分组”的问题，显然浪费。分组的数量最多 $n$ 组，每组平均只有几个点——这就是优化的入口。

正解

关键观察一：局域网就是强连通分量

先确认“同一局域网”到底该怎么理解。

题面说“存在 $A$ 到 $B$ 的连接的同时也存在 $B$ 到 $A$ 的连接，那么 $A$ 和 $B$ 处于同一局域网内”。这句话容易被读成“只有 $A$ 、 $B$ 之间直接存在一对反向边时才算同一局域网”。但这个读法是错的，样例 2 就能证明：

text

它的边是 $1\to2$ 、 $2\to3$ 、 $3\to4$ 、 $4\to2$ 、 $3\to5$ 。逐条检查可以发现，这张图里没有任何一对点之间存在直接的反向边（ $2\to3$ 有， $3\to2$ 没有； $3\to4$ 有， $4\to3$ 没有……一对都没有）。

若按“直接反向边才免费”计算，最短路径只能是 $1\to2\to3\to5$ ，耗时 $1+6+2=9$ ；
而官方答案是 $3$ 。

答案 $3$ 从哪来？ $2,3,4$ 构成环 $2\to3\to4\to2$ ，在这三个点之间任意走动都是“本地传输”，耗时 $0$ 。于是 $1 \to 2 \to (\text{在} \{2,3,4\} \text{内免费走到} 3) \to 5$ 的耗时是 $1+0+2=3$ 。

所以正确的理解是：“同一局域网” = “互相可达” = “属于同一个强连通分量（SCC）”。判断标准不是“有没有直接的反向边”，而是“绕一圈能不能互相走到”。

下图画出样例 2 的结构： $\{2,3,4\}$ 因为成环而互相可达，合并成一个局域网；点 $1$ 和点 $5$ 各自单独成一个分量。

graph LR
    n1["电脑 1"] -->|1| n2["电脑 2"]
    subgraph LAN ["同一个局域网（强连通分量）"]
        n2 -->|6| n3["电脑 3"]
        n3 -->|1| n4["电脑 4"]
        n4 -->|1| n2
    end
    n3 -->|2| n5["电脑 5"]

观察重点：局域网内部的三条边总权是 $6+1+1=8$ ，但因为是环形结构，走一圈能回到原点，所以内部任意两点之间的实际耗时都是 $0$ ；真正要付费的只有离开局域网的 $1\to2$ 和 $3\to5$ 两条边，合计 $1+2=3$ 。这也解释了为什么“直接反向边”的读法会漏掉这个局域网——环上的每条边都是单向的，但绕一圈就形成了互相可达。

关键观察二：局域网内部耗时确实为 0

上面的例子说明了直觉，这里补上严格理由。

设 $u$ 、 $v$ 在同一 SCC。取一条 $u \to v$ 的路径 $u=x_0,\ x_1,\ \dots,\ x_k=v$ 。由于 $v$ 也能到达 $u$ ，这条路径上的每个中间点 $x_i$ 都同时满足“ $u$ 能到 $x_i$ ”和“ $x_i$ 能到 $v$ 能到 $u$ ”，即 $x_i$ 与 $u$ 互相可达；相邻的 $x_i$ 与 $x_{i+1}$ 自然也互相可达。于是路径上的每一跳都能按“本地传输”免费通过，整条路径耗时 $0$ 。

注意这个论证用到的正是“绕一圈能回来”，而不是“相邻两点有反向边”。这再次说明必须按互相可达理解。

由此得到：同一个 SCC 内部，任意两点耗时 $0$ ，整个分量可以等价地看成一个点。

关键观察三：缩点后跑最短路

既然分量内部耗时 $0$ ，那么在缩点建新图时：

分量内部的边全部丢弃（它们等价于权值 $0$ ，对最短路没有贡献）；
跨分量的边原样保留，因为跨局域网传输要按原权计费。

缩点后得到一个有向无环图。虽然它也是 DAG、可以用拓扑序 DP，但边权非负，直接用堆优化 Dijkstra 更简洁：不必处理“分量内多个入度源合并”的细节，也不会写错。

新图的起点是 belong[1]，终点是 belong[n]，答案就是 dist[belong[n]]。

实现细节：Tarjan 不能写递归

$n$ 最大 $2\times10^5$ 。如果 Tarjan 写递归，在 $1\to2\to\dots\to n$ 这样的链状数据上，递归深度会达到 $2\times10^5$ 层。本机实测（macOS，栈上限 8MB）直接 Segmentation fault: 11。

所以 main.cpp 用显式栈把递归改成循环，两个数组的分工是：

dfs_stk_u[i]：第 $i$ 层正在访问的结点；
dfs_stk_e[i]：该结点下一条待处理的出边。

一次 while 循环处理一条出边；当某点的出边遍历完，就相当于递归返回：弹出一层，并用它的 low 去更新父结点的 low，然后判断它是否为 SCC 的根。这与递归写法逐句对应，只是把函数调用栈换成了数组。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182/**
 * 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-03 10:41
 * update_at: 2026-10-03 10:48
 */
// main.cpp：洛谷 P2169 正则表达式
//
// 关键建模：题目说的“A 和 B 处于同一局域网”，正确理解是「A、B 互相可达」
// （A 能走到 B，B 也能走到 A），也就是图论里的强连通。局域网内传输耗时 0。
//
// 为什么不是“只有直接互相有边才免费”？
//   对于 A->B->C->A 这样的三元环，任意两点间都没有直接的反向边，
//   但任意两点确实互相可达。题目样例 2 正是这种图：
//       1->2(1), 2->3(6), 3->4(1), 4->2(1), 3->5(2)
//   全图没有任何一对点存在双向边；若按“直接反向边才免费”算，答案是 9，
//   而官方答案是 3（1->2 花 1，2 到 3 免费，3->5 花 2）。
//   可见“同一局域网”必须按互相可达（强连通分量）来理解。
//
// 于是算法分三步：
//   1. Tarjan 求出所有强连通分量（SCC），每个分量就是一个“局域网”；
//   2. 把每个分量缩成一个点，分量内部的边权视为 0，跨分量的边保留原权；
//   3. 在缩点后的 DAG 上用堆优化 Dijkstra 求 belong[1] 到 belong[n] 的最短路。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn = 2e5 + 5;
const int maxm = 1e6 + 5;
const ll INF = 1e18;

int n, m;

/* ---------- 原图：链式前向星存边 ---------- */
int head[maxn], nxt[maxm], to[maxm], w[maxm], ecnt;

/* ---------- Tarjan 求强连通分量 ---------- */
int dfn[maxn];             // 时间戳，0 表示还没访问过
int low[maxn];             // 能回溯到的最小时间戳
int belong[maxn];          // belong[u]：点 u 属于哪个强连通分量
int stk[maxn], top;        // 手写栈，保存当前还没定分量的点
bool in_stack[maxn];       // 点是否在栈中
int dfs_clock, scc_cnt;

/* 手写 DFS 用的两个栈（Tarjan 迭代版）。
   n 最大 2e5，递归 Tarjan 在链状图上会压到 2e5 层，直接爆栈，
   所以这里用显式栈把递归改成循环：
   dfs_stk_u[i]：第 i 层正在访问的结点；dfs_stk_e[i]：它下一条要处理的边 */
int dfs_stk_u[maxn], dfs_stk_e[maxn], dfs_stk_top;

/* ---------- 缩点后的新图 ---------- */
int nhead[maxn], nnxt[maxm], nto[maxm], nw[maxm], ne_cnt;

/* ---------- Dijkstra ---------- */
ll dist[maxn];             // 从 belong[1] 出发的最短路
bool done[maxn];           // 该点是否已经确定最短路

priority_queue< pair<ll, int>, vector< pair<ll, int> >, greater< pair<ll, int> > > pq;

void add_edge(int u, int v, int c) {
    ecnt++;
    to[ecnt] = v;
    w[ecnt] = c;
    nxt[ecnt] = head[u];
    head[u] = ecnt;
}

void add_new_edge(int u, int v, int c) {
    ne_cnt++;
    nto[ne_cnt] = v;
    nw[ne_cnt] = c;
    nnxt[ne_cnt] = nhead[u];
    nhead[u] = ne_cnt;
}

// 迭代版 Tarjan：dfn/low 打时间戳，栈里同一个 low 值的点构成一个强连通分量
void tarjan(int root) {
    dfs_stk_top = 0;
    dfs_clock++;
    dfn[root] = dfs_clock;
    low[root] = dfs_clock;
    top++; stk[top] = root; in_stack[root] = true;
    dfs_stk_top++;
    dfs_stk_u[dfs_stk_top] = root;
    dfs_stk_e[dfs_stk_top] = head[root];

    while (dfs_stk_top > 0) {
        int u = dfs_stk_u[dfs_stk_top];
        int e = dfs_stk_e[dfs_stk_top];

        if (e != 0) {
            // 先记下一条边，下次循环继续；这一句等价于递归版 for 循环的 e = nxt[e]
            dfs_stk_e[dfs_stk_top] = nxt[e];
            int v = to[e];
            if (dfn[v] == 0) {
                // v 没访问过：手动“递归”进入 v
                dfs_clock++;
                dfn[v] = dfs_clock;
                low[v] = dfs_clock;
                top++; stk[top] = v; in_stack[v] = true;
                dfs_stk_top++;
                dfs_stk_u[dfs_stk_top] = v;
                dfs_stk_e[dfs_stk_top] = head[v];
            } else if (in_stack[v]) {
                // v 在栈中说明它和 u 还在同一个分量里，可以用 dfn[v] 更新 low
                if (dfn[v] < low[u]) low[u] = dfn[v];
            }
        } else {
            // u 的边全部处理完，模拟递归返回
            dfs_stk_top--;
            if (dfs_stk_top > 0) {
                int p = dfs_stk_u[dfs_stk_top];   // 父结点
                if (low[u] < low[p]) low[p] = low[u];
            }
            // low[u] == dfn[u]：u 是这个分量的“根”，把栈里的点弹出来
            if (low[u] == dfn[u]) {
                scc_cnt++;
                while (true) {
                    int v = stk[top];
                    top--;
                    in_stack[v] = false;
                    belong[v] = scc_cnt;
                    if (v == u) break;
                }
            }
        }
    }
}

void dijkstra() {
    for (int i = 1; i <= scc_cnt; i++) {
        dist[i] = INF;
        done[i] = false;
    }
    int s = belong[1];
    dist[s] = 0;
    pq.push(make_pair(0LL, s));

    while (!pq.empty()) {
        pair<ll, int> cur = pq.top();
        pq.pop();
        int u = cur.second;
        if (done[u]) continue;      // 懒删除：过期的堆元素直接跳过
        done[u] = true;

        for (int e = nhead[u]; e != 0; e = nnxt[e]) {
            int v = nto[e];
            if (dist[u] + nw[e] < dist[v]) {
                dist[v] = dist[u] + nw[e];
                pq.push(make_pair(dist[v], v));
            }
        }
    }
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= m; i++) {
        int u, v, c;
        scanf("%d %d %d", &u, &v, &c);
        add_edge(u, v, c);
    }

    for (int i = 1; i <= n; i++) {
        if (dfn[i] == 0) tarjan(i);
    }

    // 缩点：分量内部的边不用加（耗时 0），只保留跨分量的边
    for (int u = 1; u <= n; u++) {
        for (int e = head[u]; e != 0; e = nxt[e]) {
            int v = to[e];
            if (belong[u] != belong[v]) {
                add_new_edge(belong[u], belong[v], w[e]);
            }
        }
    }

    dijkstra();
    printf("%lld\n", dist[belong[n]]);
    return 0;
}

复杂度

Tarjan 求 SCC： $O(n+m)$ ；
缩点重建： $O(n+m)$ ；
堆优化 Dijkstra： $O((n+m)\log n)$ ；

总计 $O((n+m)\log n)$ 时间、 $O(n+m)$ 空间。在 $n \leqslant 2\times10^5$ 、 $m \leqslant 10^6$ 下实测约 $0.15$ 秒。

总结

本题的难点不在算法，而在读题：

“ $A$ 与 $B$ 处于同一局域网”必须理解成“ $A$ 、 $B$ 互相可达”，而不是“ $A$ 、 $B$ 之间有直接的反向边”。样例 2 里没有任何一对直接反向边，却存在一个 $\{2,3,4\}$ 的局域网，答案 $3$ 就是证据。
而“互相可达”这个关系恰好就是强连通分量定义的等价类，于是全源可达性判断问题被 Tarjan 的线性扫描解决。
分量内部任意两点耗时 $0$ （因为环路可以免费绕回来），所以缩点后内部边全部丢弃、跨分量边保留原权。
最后在缩点图上跑堆优化 Dijkstra。数据规模要求 Tarjan 必须用迭代写法，否则链状数据会爆栈。

一句话概括：“局域网”就是强连通分量，“局域网内耗时 0”就是缩点时把内部边权视作 0。

目录