[1240] 노드사이의 거리

https://www.acmicpc.net/problem/1240

1240번: 노드사이의 거리

<문제>

임의의 두 노드에 대해서, 트리라는 특성으로 인해 경로는 항상 유일함이 보장된다.

그렇기에 최단경로 알고리즘을 사용할 필요 없이, bfs든 dfs든 그래프를 만들어서, 탐색할 뿐인 문제가 된다.

 

<소스코드>

#include <bits/stdc++.h>

using namespace std;

using pi = pair<int, int>;

int n, m;

vector<pi> adj[1001];

typedef struct {

    int idx, cost;

} state;

int f(int s, int tar) {

    bool vst[1001];

    memset(vst, 0, sizeof(vst));

    vst[s] = true;

    queue<state> q;

    q.push({s, 0});

    while (!q.empty()) {

        state cur = q.front();

        q.pop();

        if (cur.idx == tar) return cur.cost;

        for (auto& nxt : adj[cur.idx]) {

            if (vst[nxt.first] == false) {

                vst[nxt.first] = true;

                q.push({nxt.first, cur.cost + nxt.second});

            }

        }

    }

    return -1;

}

int main(void) {

    ios_base::sync_with_stdio(0);

    cin.tie(0);

    cin >> n >> m;

    int i;

    for (i = 0; i < n - 1; i++) {

        int A, B, C;

        cin >> A >> B >> C;

        adj[A].push_back({B, C});

        adj[B].push_back({A, C});

    }

    for (i = 0; i < m; i++) {

        int A, B;

        cin >> A >> B;

        cout << f(A, B) << '\n';

    }

    return 0;

}