BOJ 1240: 노드사이의 거리

#BOJ 1240: 노드사이의 거리

1240번: 노드사이의 거리

#풀이

노드의 개수와 가중치가 있는 무방향 간선을 입력 받아 노드사이의 거리를 구하는 문제이다.

 

BFS를 사용하여 시작 노드에서 목표노드까지의 거리를 더해가면 해결할 수 있다.

 

간선의 가중치를 저장할 배열, 인접리스트 를 이용하여 방문할 때마다 가중치를 더해가면 된다.

 

#코드

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
int n, m;
vector<int> adj[1001];
int dis[1001][1001];
int vis[1001];
int bfs(int x, int y) {
	fill(vis + 1, vis + 1 + n, 0);
	queue<int>q;
	q.push(x);
	while (!q.empty()) {
		int prv = q.front(); q.pop();
		for (auto nxt : adj[prv]) {
			if (nxt == y)
				return vis[prv] + dis[prv][nxt];
			if (vis[nxt] != 0)
				continue;
			q.push(nxt);
			vis[nxt] = vis[prv] + dis[prv][nxt];
		}
	}
	return 0;
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	for (int i = 1; i < n; i++) {
		int num1, num2,num3;
		cin >> num1 >> num2 >> num3;
		adj[num1].push_back(num2);
		adj[num2].push_back(num1);
		dis[num1][num2] = num3;
		dis[num2][num1] = num3;
		
	}
	for (int i = 0; i < m; i++) {
		int num1, num2;
		cin >> num1 >> num2;
		cout << bfs(num1, num2) << '\n';
	}

	return 0;
}