【AtCoder】ABC 441 D - Paid Walk

2026-01-24

実行時間制限: 2 sec / メモリ制限: 1024 MiB / Difficulty: 732 / NoviSteps: 2Q / 配点: 400 点

問題概要

$N$ 頂点 $M$ 辺の重みつき有向グラフがあり、 $i$ 番目の辺は頂点 $U_i$ から頂点 $V_i$ へ向かう辺で、コストは $C_i$ である。また、各頂点の出次数は $4$ 以下である。

次の条件を満たす頂点 $v$ を全て求めよ。

頂点 $1$ $1$ から頂点 $v$ $v$ への経路であって、次の条件を共に満たすものが存在する。ただし、同じ辺を複数回通っても良いが、通るたびに回数とコストがカウントされる。
- ちょうど $L$ 回辺を通る。
- 通った辺のコストの総和が $S$ 以上 $T$ 以下である。

制約

$1\leq N, M \leq 2\times 10^5$
$1\leq L \leq 10$
$1\leq S\leq T \leq 10^9$
$1\leq C_i\leq 10^8$
入力はすべて整数

考察

まず、「各頂点の出次数は $4$ 以下である」と「 $1\leq L \leq 10$ 」という制約に注目したい。

頂点 $1$ からスタートして、のべ $L$ 回の辺を通るような経路を探索するわけだが、そのような経路は上記の制約から $4^L \leq 4^{10} \approx 10^6$ 通りしかないことが分かる。

このくらいの探索数であれば、DFSによる全探索が十分に間に合う。

DFSは、現在の頂点、現在の辺を通った回数、現在までのコストの総和を引数として保持しながら、再帰関数として実装すればよい。

実装例

1.#include <bits/stdc++.h>
2.using namespace std;
3. 
4.#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)
5. 
6.using ll = long long;
7.template <class T>
8.using Graph = vector<vector<T>>;
9. 
10.// ======================================== //
11. 
12.struct Edge
13.{
14.    int to, cost;
15.};
16. 
17.int main()
18.{
19.    int N, M, L, S, T;
20.    cin >> N >> M >> L >> S >> T;
21.    Graph<Edge> G(N);
22.    rep(i, 0, M)
23.    {
24.        int U, V, C;
25.        cin >> U >> V >> C;
26.        U--, V--;
27.        G[U].push_back({V, C});
28.    }
29. 
30.    vector<bool> flag(N, false);
31.    auto dfs = [&](auto &&self, int now, int l, ll total_cost) -> void
32.    {
33.        if (l == L)
34.        {
35.            if (S <= total_cost && total_cost <= T)
36.            {
37.                flag[now] = true;
38.            }
39.            return;
40.        }
41. 
42.        for (auto &&edge : G[now])
43.        {
44.            self(self, edge.to, l + 1, total_cost + edge.cost);
45.        }
46.    };
47. 
48.    dfs(dfs, 0, 0, 0);
49. 
50.    rep(i, 0, N)
51.    {
52.        if (flag[i])
53.            cout << i + 1 << ' ';
54.    }
55. 
56.    return 0;
57.}