[C/C++] 백준 - 1240번 : 노드사이의 거리

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

1240번: 노드사이의 거리

문제

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

입력

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

출력

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

 

두 노드가 입력으로 주어지면 그 노드 사이의 거리를 구해주는 문제이다.

나는 DFS를 이용하여 백트래킹 기법처럼 구현하였고, 모든 경로를 확인해주는 완전탐색으로 구현해주었다.

뭐 특별히 설명할 것이 없는 간단한 문제였다.

 

#include <iostream>
#include <queue>
#include <vector>
#include <stack>
#include <string>
#include <cstring>
#include <sstream>
#include <set>
#include <unordered_set>
#include <map> 
#include <algorithm>
#include <cmath>
#include <ctime>
#define fastio ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define ENDL cout << endl
#define ll long long
#define ull unsigned long long
#define INF 18549876543
#define Mod 1000000009
#define endl '\n'
#define pil pair<int,int>

using namespace std;

int N, M, cost = INF;
bool visited[1003];
vector<pair<int, int>> adj[1003];

void dfs(int from, int to, int prev, int cost_edge) {
	if (from == to) {
		cost = min(cost, cost_edge);
		return;
	}

	for (auto s : adj[from]) {
		if (!visited[s.first]) {
			visited[s.first] = true;
			dfs(s.first, to, from, cost_edge + s.second);
			visited[s.first] = false;
		}
	}
}

int main() {
	fastio;
	cin >> N >> M;
	for (int 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 });
	}

	while (M--) {
		int node1, node2;
		cin >> node1 >> node2;
		cost = INF;
		memset(visited, false, sizeof(visited));
		for (auto a : adj[node1]) {
			if (!visited[a.first]) {
				visited[a.first] = true;
				dfs(a.first, node2, node1, a.second);
				visited[a.first] = false;
			}
		}
		cout << cost << endl;
	}
	return 0;
}