1005 : ACM CRAFT (Dynamic Programming) (TopologicalSort) [C,C++]

The key to this problem is to sort through the topological sorting algorithm and solve the problem.

The topological sorting algorithm is to list the vertices on the graph in order.

==========================================================
public static int[] topologicalSort(boolean[][] adj, int[] indegree, int[] time)
{
    Queue<Integer> q = new LinkedList<>();
    int len = indegree.length;
    int[] result = new int[len];
    for (int i = 1; i < len; i++) {
        if (indegree[i] == 0) {
            result[i] = time[i];
            q.add(i);
            break;
        }
    }
    while (!q.isEmpty()) {
        int v = q.poll();
        for (int i = 1; i < len; i++) {
            if (adj[v][i]) {
                result[i] = Math.max(result[i], result[v] + time[i]);
                if (--indegree[i] == 0) {
                    q.add(i);
                }
            }
        }
    }
    return result;
}
==========================================================
<topological sorting algorithm>

topologicalSort Reference link

http://jason9319.tistory.com/93

출처: http://mygumi.tistory.com/178

The principle of the problem is not to obtain the minimum time, but to obtain the maximum value from the vertices connected from the vertex.

You can use this method to find the answer you want.

*Source of the problem = https://www.acmicpc.net/problem/1005

*문제 출처 : BAEKJOON ONLINE JUDGE