โจทย์
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
เพราะกราฟไม่มีวงจร จึงสรุปผลของแต่ละโหนดได้หลังจากประมวลผล predecessor ทั้งหมดแล้ว
คำใบ้ 2
เรียงโหนดตาม topological order แล้ว relax outgoing edges เพื่อสร้างความยาวเส้นทางที่ดีที่สุดไปยังแต่ละโหนด
คำใบ้ 3
ถ้ากราฟมีหลาย component หรือไม่มี edge คำตอบก็ควรสะท้อนเส้นทางที่ยาวที่สุดที่เข้าถึงได้
ความซับซ้อนที่คาดหวัง
เวลา O(n + m), หน่วยความจำเพิ่ม O(n + m)
แหล่งอ้างอิง
โจทย์นี้ปรับให้เหมาะกับ CodeUtility กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน