BOJ #1005 ACM Craft

There are many kinds of algorithms related to graph theory, and there are various solutions to solve one problem.

Algorithms consisting of prim, Dijkstra, and A * are the same, but the only difference is to find and update adjacent nodes.

Floyd Warshal, Krscal, and so on. This topology sort algorithm is simple enough to memorize it.

 

This problem difficulty ranked Gold II (about top 60% solver can solve this problem).

 

topology sort

The problem itself is similar to the tech tree of strategy simulation games like StarCraft. However, it is a matter of finding the shortest time that the final tech tree is made through phase alignment.


The problem is as follows:

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

1005번: ACM Craft

Since the topology sort is also a graph problem, you need to decide whether to use adjacent nodes or adjacent lists.

I've been using adjacency lists using linked lists for a while, but it's not bothersome. Nowadays we just use vector data structures.

The key of topology sort is the process of eliminating output edges by selecting nodes with no input edges. As long as the graph does not cycle, you can eventually visit all connected nodes.

Below is my source. See the source for reference only.

//--------------------------------------------------------------------
//  baekjoon #1005 - ACM Craft
//    - by Aubrey Choi
//    - created at 2019-05-31
//--------------------------------------------------------------------
#include <stdio.h>
#include <memory.h>
#include <queue>
#include <vector>

int main()
{
  int t, d[1000], node[1000], c[1000], n, k, w, from, to, i;
  char adj[1000][1000];
  scanf("%d", &t);
  while(t--)
  {
    scanf("%d%d", &n, &k);
    std::queue<int> q;
    std::vector<int> adj[n];
    memset(node, 0, n*sizeof(int));
    memset(c,0,n*sizeof(int));
    for(i=0;i<n;i++) scanf("%d",d+i);
    while(k--)
    {
      scanf("%d%d", &from, &to); from--,to--;
      adj[from].push_back(to);
      c[to]++;
    }
    for(i=0;i<n;i++) if(!c[i]) q.push(i);
    scanf("%d", &w); w--;
    for(;;)
    {
      int s=q.front(); q.pop();
      if(s==w) break;
      for(auto j:adj[s])
      {
        int v = node[s] + d[s];
        if(v > node[j]) node[j] = v;
        if(!(--c[j])) q.push(j);
      }
    }
    printf("%d\n", node[w]+d[w]);
  }
  return 0;
}