백준 1240번, 노드사이의 거리 풀이

문제

백준 1240번

풀이

나가는 간선의 개수가 $ N - 1 $이고, 정점의 개수가 $ N $이므로 SPFA를 통해 구현하는 경우 최악의 시간 복잡도는 $ O(N^2) $이 됩니다. 테스트케이스의 개수가 $ M (\leq 1000) $이므로 최악의 경우 $ O(MN^2) $이 되어 TLE가 날 것 같이 생겼습니다.

하지만, 같은 그래프에 대해서 그러한 최악의 경우가 $ M $개가 되는 경우는 없다는 믿음을 가지고 SPFA를 사용하여 구현해봅시다.

16ms에 AC가 나오는 것을 볼 수 있습니다.

소스코드

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;

vector<pii> graph[1001];
vector<int> dist, inQ;

int solve(int start, int goal) {
	dist[start] = 0;
	inQ[start] = 1;
	queue<int> q;
	q.push(start);

	while (!q.empty()) {
		int top = q.front(); q.pop();
		for (const auto &nxt : graph[top]) {
			if (dist[top] + nxt.second < dist[nxt.first]) {
				dist[nxt.first] = dist[top] + nxt.second;
				if (!inQ[nxt.first]) {
					inQ[nxt.first] = 1;
					q.push(nxt.first);
				}
			}
		}
		inQ[top] = 0;
	}


	return dist[goal];
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(nullptr);
	cout.tie(nullptr);

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

	for (int i = 0; i < m; i++) {
		int a, b, ans;
		cin >> a >> b;
		inQ.assign(1001, 0);
		dist.assign(1001, 1e9);

		cout << solve(a, b) << "\n";
	}
}