[C++] 백준 1446번: 지름길

문제 링크

1446번: 지름길

문제 요약

길이가 D 킬로미터인 고속도로를 지나는데, 고속도로에는 지름길들이 존재한다. 이 때, 고속도로를 지나기 위해 지나야 하는 거리의 최솟값을 구해야 한다.

접근 방법

D는 최대 10000 정도입니다. 이 도로를 0부터 D까지 D + 1개의 정점을 지닌 그래프로 정의할 수 있습니다. 그리고 모든 i번 정점과 i + 1번 정점 사이에는 가중치가 1인 간선을 가지고 있다고 정의할 수 있습니다. 지름길의 경우도 간선으로 정의할 수 있습니다.

지름길의 수는 12개 이하입니다. 따라서 이 문제에서 정점의 수는 최대 10001개, 간선의 수는 최대 10012개가 됩니다. 이제 0번 정점에서 D번 정점까지의 최단경로를 구해주면 됩니다.

우선순위큐를 이용한 다익스트라 알고리즘의 시간복잡도는 $O((V+E)logV)$입니다. 따라서 다익스트라 알고리즘을 이용하면 쉽게 해결할 수 있습니다.

코드

#include <bits/stdc++.h>

using namespace std;

const int MAX = 10001, INF = 1e9;
int dist[MAX];
vector<pair<int, int>> adj[MAX];

int main(void)
{
	int n, d;
	cin >> n >> d;

	for (int i = 0; i <= d - 1; i++)
		adj[i].push_back({ i + 1, 1 });

	for (int i = 0; i < n; i++)
	{
		int s, e, l;
		cin >> s >> e >> l;

		adj[s].push_back({ e, l });
	}

	fill_n(dist, MAX, INF);

	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
	pq.push({ 0, 0 });
	dist[0] = 0;

	while (!pq.empty())
	{
		auto now = pq.top();
		pq.pop();

		if (now.first > dist[now.second])
			continue;

		for (auto& i : adj[now.second])
		{
			pair<int, int> next = { now.first + i.second, i.first };
			
			if (next.first < dist[next.second])
			{
				dist[next.second] = next.first;
				pq.push(next);
			}
		}
	}

	cout << dist[d];
	return 0;
}