[백준OJ] 1240번 노드사이의 거리

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

1240번: 노드사이의 거리

---

 

-풀이-

N과 M의 값이 크지않기 때문에, 트리를 만든 뒤, 두 노드를 입력받아 BFS알고리즘을 실행하여 두 점사이의 최소거리를 구해준다.

 

-시간복잡도-

BFS의 시간복잡도는 O(V+E)가 된다. V=N이고 E=N-1이기 때문에 결국 시간복잡도는 O(N)이 된다.

이 BFS를 M번 실행하므로 최종 시간복잡도는 O(NM)이 된다.

 

-코드-

#include<iostream>
#include <algorithm>
#include<vector>
#include<queue>
#include<utility>
#define MAX 987654321
using namespace std;

int N, M;
vector<pair<int, long long>> v[1001];
long long dist[1001];

void bfs(int a,int b) {
	priority_queue<pair<long long,int>> pq;//dist,to 페어로 우선순위 큐 저장
	pq.push(make_pair(0, a));

	for (int i = 1; i <= N; i++) dist[i] = MAX;
	dist[a] = 0;

	while (!pq.empty()) {
		int now = pq.top().second;
		long long dpdist = -1*pq.top().first;
		pq.pop();
		for (int i = 0; i < v[now].size(); i++) {
			int next = v[now][i].first;
			int nowdist = v[now][i].second;

			if (nowdist + dpdist < dist[next]) {
				dist[next] = nowdist + dpdist;
				pq.push(make_pair(-1*dist[next],next));
			}
		}
	}

}

int main() {
	cin >> N >> M;
	for (int i = 0; i < N - 1; i++) {
		int x, y, w;
		cin >> x >> y >> w;
		v[x].push_back(make_pair(y, w));
		v[y].push_back(make_pair(x, w));
	}
	for (int i = 0; i < M; i++) {
		int a, b;
		cin >> a >> b;
		bfs(a, b);
		cout << dist[b]<<"\n";
	}
	return 0;
}