[1005] ACM Craft

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

1005번: ACM Craft

<문제>

각 테스트 케이스의 입력은 정점의 개수, 간선의 개수, DAG를 만족하는 간선 데이터, 목표 정점으로 이루어져 있다.

입력이 DAG를 만족하는 이유는 다음 문장에서 찾을 수 있다.

"건설순서는 모든 건물이 건설 가능하도록 주어진다."  

 

다익스트라 문제와 유사한 방식으로 생각해보자.

모든 정점까지의 최단거리를 알아낸다는 생각으로 dist[N]을 구성해줄 것이다.( N : 정점의 개수)

여기에 위상정렬을 이용해 dist[]를 채워나가는 순서를 정하도록 하고,

각 상태( == 현재 정점)마다 아래의 식으로 해당 건물까지의 최단거리를 업데이트 해줄 수 있다.

a[]는 해당 건물을 건설하는데 걸리는 시간(==가중치), dist[]는 해당 건물을 지을때의 최적해가 들어있다.

dist[next] = max(dist[cur]+a[next], dist[next])

 

N개의 정점을 모두 탐색했다면( == queue가 비었다면) 구해야하는 정답은 dist[e]에 저장되어 있다.

<소스코드>

#include <bits/stdc++.h>
using namespace std;
int indegree[1001], dist[1001], t, n, k, e;
int main(void) {
    int i, j;
    cin >> t;
    while (t--) {
        memset(indegree, 0, sizeof(indegree));
        memset(dist, 0, sizeof(dist));
        cin >> n >> k;
        vector<int> a(n + 1);
        for (i = 1; i <= n; i++) cin >> a[i];
        vector<int> adj[1001];
        for (i = 0; i < k; i++) {
            int x, y;
            cin >> x >> y;
            adj[x].push_back(y);
            indegree[y]++;
        }
        cin >> e;
        queue<int> q;
        for (i = 1; i <= n; i++) {
            if (indegree[i] == 0) {
                q.push(i);
                dist[i] = a[i];
            }
        }
        while (!q.empty()) {
            int cur = q.front();
            q.pop();
            for (auto& x : adj[cur]) {
                indegree[x]--;
                if (indegree[x] == 0) q.push(x);
                dist[x] = max(dist[cur] + a[x], dist[x]);
            }
        }
        cout << dist[e] << '\n';
    }
    return 0;
}