Official
H - 最短経路/Shortest Path Editorial by Nyaan
まずは 問題を簡単にして、 \(i\) を固定した場合を考えてみましょう。
\(i\) を始点とする深さ優先探索 (DFS) を行うことで、全ての \(j\) に対して \(i - j\) 間の距離を \(\mathrm{O}(N)\) で求めることができることが知られています。
よって、深さ優先探索で 全ての距離を列挙したあとに 距離が \(X\) であるような頂点対が存在するかを調べれば \(\mathrm{O}(N)\) でこの問題を解くことができます。
元の問題も上記のアルゴリズムを利用すれば解くことができます。
すなわち、全ての \(i\)に対して \(i\) を始点とする DFS を行えば、 \(\mathrm{O}(N)\) の操作を \(N\) 回行って全ての頂点対に対して長さが \(X\) のものが存在するか判定することができます。計算量は \(\mathrm{O}(N \times N) = \mathrm{O}(N^2)\) となり、与えられた制約内では十分高速に解くことができます。
C++ での実装例を以下に載せます。
#include <iostream>
#include <utility>
#include <vector>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (n); i++)
ll N, X;
vector<vector<pair<ll, ll>>> g;
bool ok = false;
void dfs(int c, int p, ll len) {
if (len == X) ok = true;
for (auto& [d, w] : g[c]) {
if (d == p) continue;
dfs(d, c, len + w);
}
}
int main() {
cin >> N >> X;
g.resize(N);
rep(i, N - 1) {
ll a, b, c;
cin >> a >> b >> c;
--a, --b;
g[a].emplace_back(b, c);
g[b].emplace_back(a, c);
}
rep(i, N) dfs(i, -1, 0);
cout << (ok ? "Yes" : "No") << "\n";
}
posted:
last update: