一次交易拆成买入价与卖出价两个独立的极值传播：正图从 1 做 min 松弛求路径最低买价，反图从 n 做 max 松弛求路径最高卖价，枚举分割点取差值最大。
OJ: roj
题目 ID: 3181
难度:提高+/省选-
标签:图论SPFA最短路模型
创建: 2026-10-01 23:44
更新: 2026-10-10 13:00
形式化题目
给定一张
从点
::: tip 样例解释
价格依次为
答案 5 的走法：
正解
思路
朴素做法：枚举买入点
第一步优化：只枚举分割点。 把一次交易对应到旅程
这里说「走法」而不是「简单路径」：允许重复经过点，样例里
为什么两个量可以独立取最优：对任意真实旅程（在
第二步：两个极值各自是一个单源传播问题。
第三步：用什么算法做传播。 松弛式 inq 数组防止重复入队。注意这里不能用堆优化的 Dijkstra 贪心——min/max 合并的松弛不满足 Dijkstra 所依赖的距离单调性质（比如
最后答案为
只统计「1 能到
混合图的处理：双向边
下面这张图展示正反两个方向的传播（样例的前 4 个点）：
graph LR A["1号 价格4<br/>mn=4"] -->|单向| B["2号 价格3<br/>mn=3"] B -->|双向| C["3号 价格5<br/>mn=3"] A -->|单向| D["4号 价格6<br/>mn=4"]
正图从 1 号沿实线箭头传播「到此为止的最低价」：
代码
/**
* 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-10 13:00
* update_at: 2026-10-10 13:00
*/
// 最优贸易：正图 SPFA 求最小买价，反图 SPFA 求最大卖价
#include <cstdio>
#include <vector>
using namespace std;
typedef long long ll;
const ll INF = 1LL << 60;
int n, m;
vector<int> xs, ys, zs; // 原始边表：zs = 1 单向，2 双向
vector<int> head, nxt, to;
vector<ll> price, best;
vector<char> inq;
// 链式前向星建图；z=2 的双向边在两个方向各挂一条
void build_graph() {
int E = (int)xs.size();
head.assign(n + 1, 0);
nxt.assign(2 * E + 1, 0);
to.assign(2 * E + 1, 0);
int cnt = 1; // 边从 1 号开始编号，head 为 0 表示没有出边
for (int i = 0; i < E; i++) {
int u = xs[i], v = ys[i];
to[cnt] = v; nxt[cnt] = head[u]; head[u] = cnt++;
if (zs[i] == 2) {
to[cnt] = u; nxt[cnt] = head[v]; head[v] = cnt++;
}
}
}
// 从 start 出发沿边传播路径上价格的极值；mode = 0 取 min（最小买价），1 取 max（最大卖价）
void spfa(int start, ll init, int mode) {
best.assign(n + 1, init);
inq.assign(n + 1, 0);
best[start] = price[start];
vector<int> q;
q.push_back(start);
inq[start] = 1;
for (int h = 0; h < (int)q.size(); h++) {
int u = q[h];
inq[u] = 0;
for (int e = head[u]; e; e = nxt[e]) {
int v = to[e];
ll nd = mode ? (best[u] > price[v] ? best[u] : price[v])
: (best[u] < price[v] ? best[u] : price[v]);
bool better = mode ? (nd > best[v]) : (nd < best[v]);
if (better) {
best[v] = nd;
if (!inq[v]) {
inq[v] = 1;
q.push_back(v);
}
}
}
}
}
int main() {
if (scanf("%d %d", &n, &m) != 2) {
return 0;
}
price.assign(n + 1, 0);
for (int i = 1; i <= n; i++) {
scanf("%lld", &price[i]);
}
xs.assign(m, 0); ys.assign(m, 0); zs.assign(m, 0);
for (int i = 0; i < m; i++) {
scanf("%d %d %d", &xs[i], &ys[i], &zs[i]);
}
// 正图上从 1 做 min：mn[v] = 从 1 走到 v 的路上能买到的最低价
build_graph();
spfa(1, INF, 0);
vector<ll> mn = best;
// 反图上从 n 做 max：mx[v] = 从 v 走到 n 的路上能卖出的最高价
for (int i = 0; i < m; i++) {
int t = xs[i];
xs[i] = ys[i];
ys[i] = t;
}
build_graph();
spfa(n, -INF, 1);
vector<ll> mx = best;
ll ans = 0; // 买卖都发生在 v：两头都可达才有定义
bool found = false;
for (int v = 1; v <= n; v++) {
if (mn[v] != INF && mx[v] != -INF) {
ll cand = mx[v] - mn[v];
if (!found || cand > ans) {
ans = cand;
found = true;
}
}
}
if (!found) {
ans = 0;
}
printf("%lld\n", ans);
return 0;
}#!/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-01 23:44
# update_at: 2026-10-01 23:44
import sys
from collections import deque
from operator import gt, lt
INF = 1 << 60
def build_csr(n: int, edges: list[tuple[int, int, int]]) -> tuple[list[int], list[int], list[int]]:
"""把边表建成链式前向星；z=2 的双向边在两个方向各挂一条。返回 (head, nxt, to)。"""
head = [0] * (n + 1)
nxt = [0] * (2 * len(edges) + 1)
to = [0] * (2 * len(edges) + 1)
cnt = 1 # 边从 1 号开始编号，head 为 0 表示没有出边
for x, y, z in edges:
pairs = [(x, y), (y, x)] if z == 2 else [(x, y)] # 双向边存两条
for u, v in pairs:
to[cnt] = v
nxt[cnt] = head[u]
head[u] = cnt
cnt += 1
return head, nxt, to
def spfa(n: int, head: list[int], nxt: list[int], to: list[int], price: list[int],
start: int, init: int, combine, is_better) -> list[int]:
"""从 start 出发，沿边传播“路径上价格的极值”：combine=min 得最小买价，=max 得最大卖价。
best[v] = 起点到 v 的所有路径上，combine(路径上各点价格) 的最优值；
每次松弛取 combine(best[u], price[v])，队列 + inq 就是标准 SPFA。
不可达点保持初值 init：min 版为 INF，max 版为 -INF。
"""
best = [init] * (n + 1)
best[start] = price[start]
inq = bytearray(n + 1)
inq[start] = 1
dq = deque([start])
while dq:
u = dq.popleft()
inq[u] = 0
e = head[u]
while e:
v = to[e]
nd = combine(best[u], price[v])
if is_better(nd, best[v]):
best[v] = nd
if not inq[v]:
inq[v] = 1
dq.append(v)
e = nxt[e]
return best
def solve() -> None:
data = iter(map(int, sys.stdin.buffer.read().split()))
n, m = next(data), next(data)
price = [0] + [next(data) for _ in range(n)]
edges = [(next(data), next(data), next(data)) for _ in range(m)]
# 正图上从 1 做 min：mn[v] = 从 1 走到 v 的路上能买到的最低价
head, nxt, to = build_csr(n, edges)
mn = spfa(n, head, nxt, to, price, 1, INF, min, lt)
# 反图上从 n 做 max：mx[v] = 从 v 走到 n 的路上能卖出的最高价
rhead, rnxt, rto = build_csr(n, [(y, x, z) for x, y, z in edges])
mx = spfa(n, rhead, rnxt, rto, price, n, -INF, max, gt)
# 买卖都发生在 v：两头都可达才有定义，等初值说明该端不可达
print(max((s - b for b, s in zip(mn, mx)
if b != INF and s != -INF), default=0))
if __name__ == "__main__":
solve()复杂度
- 时间：两次 SPFA 型松弛，均摊
（ 为小常数；与 SPFA 求最短路的最坏情形一样，理论上限 ，实践中远小于此），外加枚举分割点 。对 、 的加强数据，Python 实测最慢约 0.15s。 - 空间：链式前向星存至多
条弧 × 正反两份， ；两轮松弛各一个值数组， 。
样例走法
把样例的 5 个城市列成表，标出每个点经过两次传播后的
| 城市 |
价格 |
|||
|---|---|---|---|---|
| 1 | 4 | 4 | 6 | 2 |
| 2 | 3 | 3 | 6 | 3 |
| 3 | 5 | 3 | 6 | 3 |
| 4 | 6 | 4 | 6 | 2 |
| 5 | 1 | 1 | 6 | 5 |
观察这张表：
沿「 」被 2 号的低价（3 元）刷新后一路下传；到 5 号时被 刷到 1。 被价格最高的 4 号（6 元）主导：双向边 让 、 互相刷新都变成 6—— 的含义是「从 5 号先走到 4 号、再回 5 号」这条走法上最高能以 6 元卖出。 - 最大差值出现在
：在 5 号以 1 元买入、去 4 号以 6 元卖出，利润 5，与样例输出一致。 - 注意
在 上只有 2： 看似不错，但分割点模型允许每个 独立取两侧最优，枚举完所有点自然选中 ，无需比较不同「方案」。
总结
- 一次交易 = 走法上的一个分割点；枚举分割点把
的点对枚举降为 ，并顺带正确处理「重复经过点」的环。 - 「走法上价格的 min/max」是与最短路同构的单源传播问题：正图从 1 做 min、反图从
做 max，同一个 SPFA 型松弛函数参数化后跑两遍；不能用 Dijkstra 贪心。 - 答案
，只统计两侧都可达的点，无正利润输出 0。 - 该模型（正反两遍带约束极值 + 枚举分割点）是「路径上先买后卖」一类问题的通用套路，可直接迁移到「两次旅行拼接」「路径最长边最小化」等变体。