1005번: ACM Craft - 다익스트라, 위상 정렬

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

1005번: ACM Craft

 

1. 건물 하나를 지을 때 미리 지어야 하는 건물들이 있으며, 건물 하나를 지을 때 걸리는 시간은 미리 지어야 하는 건물들 중 시간이 가장 오래 걸리는 건물의 시간과 같다.

2. 건물들은 동시에 건설할 수 있다.

이 두 가지를 종합하면, 건물 W를 짓기 위한 시간은 처음 지어야 하는 건물부터 건물 W를 지을 때까지 가장 오래 걸리는 시간과 같다고 할 수 있다. 즉 처음 지어야 하는 건물부터 건물 W까지의 최장 경로를 구하면 된다. 이때 간선의 가중치는 해당 건물을 짓는 시간과 같다.

 

이때,

1. 처음 지어야 하는 건물이 여러 개 있을 수 있다. 이를 해결하기 위해 위상 정렬 개념을 약간 도입하여, 들어오는 간선이 없는 노드(건물)를 골라 우선순위 큐에 집어넣는다.

2. 다익스트라를 응용해 최장 경로를 구한다.

를 진행하면 된다.

#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <cmath>
#include <algorithm>
#include <string>
#include <iomanip>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

void solve();

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int T; cin >> T;
	for (int i{ 1 }; i <= T; i++) solve();
}

void solve()
{
	int N, K;
	int buildTime[1001];
	vector<pii> graph[1001];
	int enter[1001] = {};
	priority_queue<pii, vector<pii>, greater<pii>> pq;
	vector<int> dist(1001, -1);

	cin >> N >> K;
	for (int i{ 1 }; i <= N; i++) cin >> buildTime[i];
	for (int i{ 1 }; i <= K; i++)
	{
		int X, Y; cin >> X >> Y;
		graph[X].push_back({ Y, buildTime[Y] });
		enter[Y]++;
	}
	int W; cin >> W;

	for (int i{ 1 }; i <= N; i++)
	{
		if (enter[i] == 0)
		{
			pq.push({ buildTime[i], i});
			dist[i] = buildTime[i];
		}
	} //위상 정렬을 응용해 처음 지어야 하는 건물을 알아낸다.

	while (!pq.empty())
	{
		auto [d, u] = pq.top(); pq.pop();
		if (dist[u] < d) continue;

		for (auto [v, w] : graph[u])
		{
			if (dist[v] < dist[u] + w)
			{
				dist[v] = dist[u] + w;
				pq.push({ dist[v], v });
			}
		}
	} //다익스트라로 최장 경로를 구한다.
	cout << dist[W] << "\n";
}