🔗 Problem #1005

In the year 2012! The game ACM Craft (Association of Construction Manager Craft), which has kept countless citizens waiting for two years, has finally been released.

Unlike previous games, ACM Craft does not have a fixed order for constructing buildings, allowing for dynamic gameplay. In other words, the first game and the second game may have a different building order. At the start of each game, the building order is given. Also, every building has a delay from the start of construction until its completion.

Let's look at the example above.

In this game, the following construction order rules are given. Once the construction of building 1 is complete, construction of buildings 2 and 3 can begin. (They can proceed simultaneously.) And in order to build building 4, both buildings 2 and 3 must be completed before construction of building 4 can begin.

Therefore, to complete building 4, it first takes 10 seconds to build building 1. Then, if construction of buildings 2 and 3 starts simultaneously, building 2 is completed 1 second later, but building 3 is not yet complete, so building 4 cannot be built. Once building 3 is complete, building 4 can then be built, so a total of 120 seconds is required to complete building 4.

Pro gamer Choi Baekjoon entered the Sogang University ACM Craft tournament to raise money for a date with his girlfriend! Since Choi Baekjoon has brilliant control skills, he can win any match unconditionally if he only builds a specific building. However, since the construction order for the specific building changes every game, Choi Baekjoon has been frustrated. For Baekjoon's sake, let's write a program that figures out the minimum time it takes to build the specific building as fast as possible.

The first line contains the number of test cases $T$. Each test case is given as follows: the first line contains the number of buildings $N$ and the total number of construction order rules between buildings $K$. (Buildings are numbered from 1 to $N$.)

The second line gives the construction time $D$ for each building, separated by spaces. From the third line to line $K + 2$, the construction order $X$ $Y$ is given. (This means that building $Y$ can be built after building $X$ is built.)

The last line gives the number $W$ of the building that Baekjoon must build in order to win.

Print the minimum time required to finish building $W$. For convenience, assume that issuing the command to build a building takes no time. The construction order is given such that all buildings can be built.

• $2 ≤ N ≤ 1,000$
• $1 ≤ K ≤ 100,000$
• $1 ≤ X, Y, W ≤ N$
• $0 ≤ D ≤ 100,000)$ $D$ is an integer

• Input

TC
2
4 4
10 1 100 10
1 2
1 3
2 4
3 4
4
8 8
10 20 1 5 8 7 1 43
1 2
1 3
2 4
2 5
3 6
5 7
6 7
7 8
7

• Output

TC
120
39

• Input

TC
5
3 2
1 2 3
3 2
2 1
1
4 3
5 5 5 5
1 2
1 3
2 3
4
5 10
100000 99999 99997 99994 99990
4 5
3 5
3 4
2 5
2 4
2 3
1 5
1 4
1 3
1 2
4
4 3
1 1 1 1
1 2
3 2
1 4
4
7 8
0 0 0 0 0 0 0
1 2
1 3
2 4
3 4
4 5
4 6
5 7
6 7
7

• Output

TC
6
5
399990
2
0

The problem is easy to understand, but it was an algorithm that was hard to solve through code. You need to understand topological sort. For this problem, you can approach it similarly to the building tech tree in StarCraft. Just as you must build a barracks before you can build a factory, if a building has a prerequisite tree, that building must be completed first, and a single building may have multiple prerequisites. Of course, in that case, construction is possible only after all required buildings have been built. It's not enough to build just one of the required buildings.

Topological sort is an algorithm that determines the order in which tasks with a fixed order must be performed. Topological sort must be applied to a DAG (Directed Acyclic Graph). That is, when the order is diagrammed, there must always be a start point and an end point. If it's a cyclic structure where start and end points cannot be distinguished, topological sort cannot be applied.

Topological sort is an algorithm for determining order, and various answers can result depending on the shape of the flowchart. For this problem, in order to derive the optimal answer, I applied the required buildings needed to build each building and the construction time.

Since all required buildings must be built before the next building can be built, the building whose required-building construction time is the greatest becomes the next in order.

If we diagram the topological sort using the second case of example 1, we get the picture above.

The table above summarizes and quantifies the diagram.

1. Find the starting point of the order (a point with no incoming edges). If there are multiple starting points, you may pick any one of them at random. (In this example, there is only one starting point.)

2. Add starting point 1 to the queue, and remove all outgoing edges connected to the starting point.

In this process, we can see that 2 and 3 have become new starting points.

The time it takes to build 1 is 1 second.

3. Apply step 2 to node 2.

The in-degree of 4 and 5 becomes 0. That is, 4 and 5 can now be built.

Building 2 takes a total of $10(1) + 20(2)$ = 30 seconds.

4. Apply step 2 to node 3.

The in-degree of 6 becomes 0. Building 6 can now be built.

The construction time for 3 is $10(1) + 1(3)$, a total of 11 seconds.

5. Apply step 2 to node 4.

Since 4 has no outgoing edges, it's simply added to the queue.

Building 4 takes a total of $10(1) + 20(2) + 5(4)$ = 35 seconds

6. Apply step 2 to node 5.

Since 7 is connected to both 5 and 6, the in-degree of 7 becomes 1. Building 7 still cannot be built.

Building 5 takes a total of $10(1) + 20(2) + 8(5)$ = 38 seconds

7. Apply step 2 to node 6.

The in-degree of 7 becomes 0. Building 7 can now be built.

The construction time for 6 is $10(1) + 1(3) + 7(6)$, a total of 18 seconds.

8. Apply step 2 to node 7.

The in-degree of 8 becomes 0.

Buildings 1 through 6 each had only one prerequisite, but 7 has two. As mentioned earlier, we need to calculate based on whichever of 5 and 6 has the longer construction time.

That is, the construction time of 7 is $10(1) + 20(2) + 8(5) + 1(7)$, a total of 39 seconds

Since the calculation is based on building 5, building 6 and the intermediate building 3 are excluded from the calculation. If the construction time of building 3 were increased from 1 second to 4 seconds, it wouldn't affect the result, because building 3's construction time is ignored. However, if building 3's construction time became too large, the construction time of building 6 would also grow larger than that of building 5, and it would then affect the result.

9. Apply step 2 to node 8.

Since the problem asks for the construction time for building 7, building 8 can be ignored. Building 8's construction time is $10(1) + 20(2) + 8(5) + 1(7) + 43(8)$, a total of 82 seconds

The time, matrix, and link arrays have a size of $N + 1$. There's no particular reason for this — buildings start numbering from 1, but arrays start from index 0. To avoid confusion from this difference, if there are 4 buildings in total, the array size is set to 5 (0, 1, 2, 3, 4, 5), and index 0 is left unused, starting from 1.

JAVA
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

/**
 * Baekjoon problem #1005 algorithm class
 *
 * @author RWB
 * @see <a href="https://blog.itcode.dev/posts/2021/06/01/a1005">1005 solution</a>
 * @since 2021.05.31 Mon 19:11:58
 */
public class Main
{
	/**
	 * Main function
	 *
	 * @param args: [String[]] arguments
	 */
	public static void main(String[] args)
	{
		Scanner scanner = new Scanner(System.in);
		
		StringBuilder builder = new StringBuilder();
		
		// Number of cases
		int T = scanner.nextInt();
		
		for (int i = 0; i < T; i++)
		{
			// Number of buildings
			int N = scanner.nextInt();
			
			// Number of rules (construction dependencies)
			int K = scanner.nextInt();
			
			// Array of construction time per building
			int[] time = new int[N + 1];
			
			// Array of connection status between buildings
			boolean[][] matrix = new boolean[N + 1][N + 1];
			
			// Array of connection count per building
			int[] link = new int[N + 1];
			
			for (int j = 1; j < N + 1; j++)
			{
				time[j] = scanner.nextInt();
			}
			
			for (int j = 0; j < K; j++)
			{
				// Prerequisite building
				int X = scanner.nextInt();
				
				// Dependent building
				int Y = scanner.nextInt();
				
				matrix[X][Y] = true;
				link[Y]++;
			}
			
			// Target building
			int W = scanner.nextInt();
			
			builder.append(calcTopologicalSort(time, matrix, link)[W]).append("\n");
		}
		
		System.out.println(builder.toString());
		
		scanner.close();
	}
	
	/**
	 * Function that returns the topological sort result
	 *
	 * @param time: [int[]] construction time per building
	 * @param matrix: [boolean[][]] connection status per building
	 * @param link: [int[]] connection count per building
	 *
	 * @return [int[]] array of total construction time per building
	 */
	private static int[] calcTopologicalSort(int[] time, boolean[][] matrix, int[] link)
	{
		Queue<Integer> queue = new LinkedList<>();
		
		int[] result = new int[link.length];
		
		for (int i = 1; i < link.length; i++)
		{
			// If the building has no prerequisites
			if (link[i] == 0)
			{
				result[i] = time[i];
				queue.add(i);
			}
		}
		
		while (!queue.isEmpty())
		{
			// Prerequisite building
			int prev = queue.poll();
			
			for (int i = 1; i < link.length; i++)
			{
				// If this building requires the prerequisite building
				if (matrix[prev][i])
				{
					result[i] = Math.max(result[i], result[prev] + time[i]);
					
					// Decrease the required-building count for this building by 1
					--link[i];
					
					// If the building has no prerequisites
					if (link[i] == 0)
					{
						queue.add(i);
					}
				}
			}
		}
		
		return result;
	}
}

• Dynamic Programming
• Graph Theory
• Topological Sort