BOJ 1240 — Distance Between Nodes

Problem: BOJ 1240 — Distance Between Nodes · 한국어 · 日本語

The input is a tree, so there is exactly one path between any two vertices. Therefore, the shortest-path distance is simply the sum of the edge weights along that unique path; no general shortest-path algorithm is needed.

For each query, traverse from its starting vertex with an explicit stack. Each stack entry carries the current vertex, its parent, and the distance accumulated from the start. Skip the parent edge so the traversal does not go back across an already-used edge. When the target is reached, print its accumulated distance and stop that query’s traversal. This is iterative, so even a chain-shaped tree does not consume the call stack.

Input vertex labels are 1-based and can be used directly with arrays sized N + 1. The given edge weights are at most 10,000, and N <= 1,000, so any path contains at most 999 edges and has length at most 9,990,000. A 64-bit integer safely stores the accumulated distance. The graph and traversal stack use O(N) memory; processing all M queries takes O(NM) time in the worst case.

C++17

#include <iostream>
#include <tuple>
#include <utility>
#include <vector>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    vector<vector<pair<int, int>>> graph(n + 1);
    for (int i = 0; i < n - 1; ++i) {
        int a, b, weight;
        cin >> a >> b >> weight;
        graph[a].push_back({b, weight});
        graph[b].push_back({a, weight});
    }

    while (m--) {
        int start, target;
        cin >> start >> target;

        vector<tuple<int, int, long long>> pending;
        pending.emplace_back(start, 0, 0);

        while (!pending.empty()) {
            auto [node, parent, distance] = pending.back();
            pending.pop_back();

            if (node == target) {
                cout << distance << '\n';
                break;
            }

            for (auto [next, weight] : graph[node]) {
                if (next != parent) {
                    pending.emplace_back(next, node, distance + weight);
                }
            }
        }
    }
}