문제
Tasks 0..n−1 form a directed acyclic graph. Each edge [u, v, w] means task v can start w hours after task u. Find the length of the longest path (the critical path). Process nodes in topological order.
Implement longest_path(n, edges).
Input
n: The number of nodes. edges: Edges as [from, to, weight].
Output
Return the total weight of the longest path (0 if there are no edges).
제약 조건
1 ≤ n ≤ 100,000; 0 ≤ edges ≤ 200,000; 1 ≤ weight ≤ 10,000; the graph has no cycles
예시
입력:
n = 4
edges = [
[0, 1, 3],
[0, 2, 2],
[1, 3, 4],
[2, 3, 6]
]
예상 출력:
expected = 8입력:
long long n = 4;
std::vector<std::vector<long long>> edges = {
{0, 1, 3},
{0, 2, 2},
{1, 3, 4},
{2, 3, 6}
};
예상 출력:
long long expected = 8;입력:
long n = 4;
long[][] edges = new long[][] {
new long[] {0, 1, 3},
new long[] {0, 2, 2},
new long[] {1, 3, 4},
new long[] {2, 3, 6}
};
예상 출력:
long expected = 8;설명
0→1→3 weighs 7, 0→2→3 weighs 8: the longest path is 8.
입력:
n = 3
edges = []
예상 출력:
expected = 0입력:
long long n = 3;
std::vector<std::vector<long long>> edges = {};
예상 출력:
long long expected = 0;입력:
long n = 3;
long[][] edges = new long[][] {};
예상 출력:
long expected = 0;설명
Without edges every path has length 0.
접근 방법
먼저 스스로 풀어 본 뒤 힌트를 하나씩 열어 보세요.
힌트 1
그래프에 사이클이 없으므로, 각 노드는 모든 선행 노드를 처리한 뒤 확정할 수 있습니다.
힌트 2
위상 정렬 후 나가는 간선을 완화해 각 노드까지의 최장 경로를 구하세요.
힌트 3
연결 요소가 여러 개이거나 간선이 없어도, 답은 가장 긴 도달 가능 경로 가중치를 반영해야 합니다.
예상 복잡도
시간 O(n + m), 추가 공간 O(n + m)
참고 자료
이 문제는 CodeUtility에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.