[백준,c++] 1240번 - 노드사이의 거리

문제

1240번: 노드사이의 거리

 

코드

#include <iostream>
#include <vector>
#include <memory.h>


#define MAX 1e9
using namespace std;


int N,M;
vector<pair<int,int>>graph[1001];
int visited[1001];

int ans;

void dfs(int x, int y, int dist){
    visited[x]=1;
    
    if(x==y){
        ans = dist;
        return;
    }
    
    for(int i=0; i<graph[x].size(); i++){
        int cost = dist + graph[x][i].second;
        int next_node = graph[x][i].first;
        if(visited[next_node]) continue;
        visited[next_node]=1;
        dfs(graph[x][i].first, y, cost) ;
    }
}


int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    cin>>N>>M;
    
    for(int i=0; i<N-1; i++){
        int a,b,dist; cin>>a>>b>>dist;
        graph[a].push_back({b,dist});
        graph[b].push_back({a,dist});
    }
    
    
    for(int i=0; i<M; i++){
        int a,b; cin>>a>>b;
        dfs(a,b,0);
        memset(visited,0,sizeof(visited));
        cout<<ans<<'\n';
    }
    
}

 

풀이

양방향으로 연결되어 있는 노드 사이의 거리를 찾는 문제입니다. 각 노드별로의 거리가 입력으로 주어지기 때문에 dfs를 통해서 정점을 파도타기 하듯이 타고 타고 들어가여 도착 노드가 되었을 때 거리를 출력하면 됩니다.