在 DAG 上同时维护从起点到每个点的路径条数和所有路径长度总和，最后加上每次重新坐船返回的固定时间。
OJ: luogu
题目 ID: P1685
难度:普及+/提高
标签:图论拓扑排序动态规划高精度
日期: 2026-06-19 23:37
题意
给一张没有环的有向图，从起点 s 走到终点 t 的每一条路径都算一种游览路线。
你要把所有不同的路线都走一遍：
- 每走完一条路线，如果还想继续走下一条路线，就要花
t0的时间从东头坐船回到西头 - 最后一条路线走完后直接离开，不需要再回去
问把所有不同路线都游览完，一共要花多少时间。
注意题目允许重边，因此即使经过的点相同，只要走的是不同的边，也算不同路线。
样例图
这张图展示样例里的 3 条路径：
digraph G {
rankdir=LR;
1 -> 2 [label="5"];
2 -> 3 [label="7"];
2 -> 3 [label="10"];
1 -> 3 [label="15"];
}
三条路线的长度分别是 12、15、15，总和为 42。
前两次游览结束后还要各坐一次船回到起点，所以再加 2 * 7。
因此答案是 42 + 14 = 56。
思路
先看一个最直接的小数据暴力：
cpp
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 20;
int n, m, s, t, t0;
struct Edge {
int to, w;
};
vector<Edge> graph[MAXN];
long long path_cnt;
long long total_len;
// 直接枚举所有从 s 到 t 的路径。
void dfs(int u, long long len) {
if (u == t) {
path_cnt++;
total_len += len;
return;
}
for (Edge e : graph[u]) {
dfs(e.to, len + e.w);
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m >> s >> t >> t0;
for (int i = 1; i <= n; i++) {
graph[i].clear();
}
for (int i = 1; i <= m; i++) {
int u, v, w;
cin >> u >> v >> w;
graph[u].push_back({v, w});
}
path_cnt = 0;
total_len = 0;
dfs(s, 0);
cout << total_len + (path_cnt - 1) * t0 << '\n';
return 0;
}暴力就是 DFS 枚举所有从 s 到 t 的路径：
- 每到终点，就把当前路径长度加到总和里
- 同时把路径条数加一
最后答案就是：
所有路径长度之和 + (路径条数 - 1) * t0
这个思路很直观，但如果路径很多，就不能真的一条一条枚举。
题目给的是 DAG，所以可以在拓扑序上做 DP。
对每个点 u 维护两个量：
cnt[u]：从s到u的路径条数sum[u]：从s到u的所有路径长度总和
如果有一条边 u -> v，边权是 w，那么：
- 所有到
u的路径都能接到v - 新增到
v的路径条数正好是cnt[u] - 这些新路径的总长度，等于原来的
sum[u]再加上每条路径多出来的一段w
所以转移是：
cnt[v] += cnt[u]sum[v] += sum[u] + cnt[u] * w
最后：
sum[t]是所有路线本身的长度总和cnt[t] - 1是需要坐船返回的次数
于是答案就是：
sum[t] + (cnt[t] - 1) * t0
因为路径条数可能非常大，long long 不够，所以代码里用了一个只支持：
- 高精加法
- 高精乘整数
的简化高精整数类，已经足够覆盖这题需要的运算。
代码
cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 10005;
const int MAXM = 50005;
const int BASE = 100000000;
const int WIDTH = 8;
struct BigInteger {
vector<int> d; // 小端存储，d[0] 是最低位
BigInteger(long long x = 0) {
*this = x;
}
void operator=(long long x) {
d.clear();
if (x == 0) {
d.push_back(0);
return;
}
while (x > 0) {
d.push_back(x % BASE);
x /= BASE;
}
}
void trim() {
while (d.size() > 1 && d.back() == 0) {
d.pop_back();
}
}
string to_string() const {
stringstream ss;
ss << d.back();
for (int i = (int) d.size() - 2; i >= 0; i--) {
ss << setw(WIDTH) << setfill('0') << d[i];
}
return ss.str();
}
};
BigInteger operator+(const BigInteger &a, const BigInteger &b) {
BigInteger c;
c.d.clear();
int n = max((int) a.d.size(), (int) b.d.size());
long long carry = 0;
for (int i = 0; i < n; i++) {
long long sum = carry;
if (i < (int) a.d.size()) {
sum += a.d[i];
}
if (i < (int) b.d.size()) {
sum += b.d[i];
}
c.d.push_back(sum % BASE);
carry = sum / BASE;
}
if (carry) {
c.d.push_back(carry);
}
c.trim();
return c;
}
BigInteger operator*(const BigInteger &a, int b) {
if (b == 0) {
return BigInteger(0);
}
BigInteger c;
c.d.clear();
long long carry = 0;
for (int x : a.d) {
long long now = 1LL * x * b + carry;
c.d.push_back(now % BASE);
carry = now / BASE;
}
while (carry) {
c.d.push_back(carry % BASE);
carry /= BASE;
}
c.trim();
return c;
}
BigInteger sub_int(BigInteger a, int b) {
int i = 0;
int borrow = b;
while (borrow > 0) {
int cur = borrow % BASE;
borrow /= BASE;
if (a.d[i] >= cur) {
a.d[i] -= cur;
} else {
a.d[i] += BASE - cur;
int j = i + 1;
while (a.d[j] == 0) {
a.d[j] = BASE - 1;
j++;
}
a.d[j]--;
}
i++;
}
a.trim();
return a;
}
int n, m, s, t, t0;
int head[MAXN], to[MAXM], nxt[MAXM], w[MAXM], indeg[MAXN], edge_cnt;
BigInteger cnt[MAXN]; // cnt[i] : 从 s 到 i 的路径条数
BigInteger sum[MAXN]; // sum[i] : 从 s 到 i 的所有路径长度总和
void add_edge(int u, int v, int val) {
edge_cnt++;
to[edge_cnt] = v;
w[edge_cnt] = val;
nxt[edge_cnt] = head[u];
head[u] = edge_cnt;
indeg[v]++;
}
void read_input() {
cin >> n >> m >> s >> t >> t0;
edge_cnt = 0;
for (int i = 1; i <= n; i++) {
head[i] = 0;
indeg[i] = 0;
cnt[i] = BigInteger(0);
sum[i] = BigInteger(0);
}
for (int i = 1; i <= m; i++) {
int u, v, val;
cin >> u >> v >> val;
add_edge(u, v, val);
}
}
void solve() {
queue<int> q;
int deg[MAXN];
memcpy(deg, indeg, sizeof(indeg));
cnt[s] = BigInteger(1);
for (int i = 1; i <= n; i++) {
if (deg[i] == 0) {
q.push(i);
}
}
while (!q.empty()) {
int u = q.front();
q.pop();
for (int i = head[u]; i != 0; i = nxt[i]) {
int v = to[i];
cnt[v] = cnt[v] + cnt[u];
sum[v] = sum[v] + sum[u] + cnt[u] * w[i];
deg[v]--;
if (deg[v] == 0) {
q.push(v);
}
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
read_input();
solve();
BigInteger ans = sum[t] + sub_int(cnt[t] * t0, t0);
cout << ans.to_string() << '\n';
return 0;
}复杂度
设点数为 n，边数为 m。
- 拓扑 DP 主流程是
- 每次高精运算的代价与当前数字位数成正比
因此总复杂度可以理解为
总结
这题的关键不是“把所有路径枚举出来”，而是看出：在 DAG 上，路径条数和路径长度总和都可以一起按拓扑序转移。真正需要额外注意的，是答案会爆普通整数，所以要补上高精。
一图流解析
这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。
