백준 1240 c++

문제

N(2≤N≤1,000)개의 노드로 이루어진 트리가 주어지고 M(M≤1,000)개의 두 노드 쌍을 입력받을 때 두 노드 사이의 거리를 출력하라.

입력

첫째 줄에 노드의 개수 N이 입력되고 다음 N-1개의 줄에 트리 상에 연결된 두 점과 거리(10,000 이하의 정수)를 입력받는다. 그 다음 줄에는 거리를 알고 싶은 M개의 노드 쌍이 한 줄에 한 쌍씩 입력된다.

출력

M개의 줄에 차례대로 입력받은 두 노드 사이의 거리를 출력한다.

예제 입력 1 복사

4 2
2 1 2
4 3 2
1 4 3
1 2
3 2

예제 출력 1 복사

2
7

 

골드5라서 긴장했으나 막상 풀어보니 어렵지않았던 문제

문제가 쉬웠던걸까 내가 조금 더 성장한걸까

 

#include <bits/stdc++.h>

using namespace std;


int N;
int M;

vector<pair<int,int>>graph[1001];

int visited[1001];

void dfs(int start , int end , int sum){
    if(start==end){

        cout << sum << "\n";

        return ;
    }
    visited[start]=1;


    for (int i = 0; i <graph[start].size() ; ++i) {
        int next = graph[start][i].first;
        int dis = graph[start][i].second;
        if(visited[next]==0){
            dfs(next,end,sum+dis);
        }
    }
}



int main(){

    cin >> N >> M;

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

    }

    for (int i = 0; i < M; ++i) {
        int x,y;
        cin >> x >> y;
        dfs(x,y,0);
        memset(visited,0,sizeof visited);
    }









}

 

문제의 로직은

 

노드를 옮길때마다 거리값을 더하고 만약에 위치에 도달하면 더해진 거리값을 출력한다 넘나 간단