C语言实现关键路径计算：案例例题与代码详解

题目：关键路径计算\n\n题目描述：\n某软件项目需要完成一系列的任务，每个任务都有一个持续时间和一个依赖关系（即它必须在其他任务完成后才能开始）。任务之间的依赖关系可以用一个有向无环图（DAG）来表示，图中的每个节点代表一个任务，边表示依赖关系。每个任务有一个唯一的编号（从1到N），并且编号越小的任务在拓扑排序中越靠前。\n\n现在需要编写一个程序，根据给定的任务信息，计算关键路径，并输出关键路径上的任务及其总持续时间。\n\n输入：\n输入的第一行包含两个整数N和M，分别表示任务的数量和依赖关系的数量。\n\n接下来的M行每行包含两个整数x和y，表示任务x依赖于任务y（即任务y必须在任务x之前完成）。\n\n接下来的N行每行包含一个整数t，表示任务的持续时间。\n\n输出：\n输出关键路径上的任务及其总持续时间。每行输出一个任务的编号和持续时间。\n\n示例：\n输入：\n5 6\n1 2\n1 3\n2 4\n3 4\n4 5\n5 3\n2\n3\n1\n4\n2\n\n输出：\n1 11\n2 4\n4 7\n5 2\n\n提示：\n在关键路径上的任务满足以下条件：\n1. 任务的入度为0；\n2. 任务的出度为0；\n3. 任务的持续时间等于从起始节点到该节点的最长路径长度。\n\n可以使用拓扑排序和动态规划的方法来解决该问题。