ACM Craft

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

주어진 문제를 그래프로 표현하자.

• u -> v 간선은 건물 u가 건물 v보다 먼저 지어져야 함을 의미한다.

• w(u, v)는 건물 u의 건설 시간으로 하자.

• 편의를 위해 아래를 가정하자.

  • 0번 건물이 존재한다고 하고,

  • 모든 건물들(1 ~ N번)은 0번 건물보다 나중에 지어져야 하며,

  • 0번 건물은 짓는데 0시간이 걸린다고 하자.

    이제 0번 건물에서 W번 건물에 이르는 최장경로를 찾고, W의 건설시간까지 더해주면 곧 답이 된다.

최장경로는 주어지는 입력이 DAG임이 보장되므로 위상정렬 + relax로 쉽게 풀어 줄 수 있다.

#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

const int kMaxN = 1000;

int T;
int N;
int K;
int DURATIONS[kMaxN + 1];
vector<vector<pair<int, int>>> ADJ;
int W;

void Dfs(const int v, vector<bool>& visit, vector<int>& topology)
{
  visit[v] = true;
  for (auto neighbor : ADJ[v])
  {
    if (!visit[neighbor.first])
    {
      Dfs(neighbor.first, visit, topology);
    }
  }

  topology.emplace_back(v);
}

int Solve(const int dst)
{
  vector<bool> visit(N + 1, false);
  vector<int> topology;

  Dfs(0, visit, topology);

  vector<int> dist(N + 1, 0);

  for (auto v = topology.rbegin(); v != topology.rend(); ++v)
  {
    int here = *v;
    for (auto neighbor : ADJ[here])
    {
      int there = neighbor.first;
      int cost = neighbor.second;

      if (dist[there] < dist[here] + cost)
      {
        dist[there] = dist[here] + cost;
      }
    }
  }

  return dist[dst];
}

int main(void)
{
  scanf(" %d", &T);
  while (T--)
  {
    scanf(" %d %d", &N, &K);
    for (int it = 1; it <= N; ++it)
    {
      scanf(" %d", &DURATIONS[it]);
    }

    ADJ.assign(N + 1, vector<pair<int, int>>());
    for (int it = 1; it <= N; ++it)
    {
      ADJ[0].emplace_back(it, 0);
    }

    for (int it = 0; it < K; ++it)
    {
      int src, dst;
      scanf(" %d %d", &src, &dst);
      ADJ[src].emplace_back(dst, DURATIONS[src]);
    }

    scanf(" %d", &W);

    printf("%d\n", Solve(W) + DURATIONS[W]);
  }

  return 0;
}