用python完成以下任务 一个项目由若干个任务组成,任务之间有先后依赖顺序。项目经理需要设置一系列里程碑,在每个里程碑节点处检查任务的完成情况,并启动后续的任务。现给定一个项目中各个任务之间的关系,请你计算出这个项目的最早完工时间。 输入格式: 首先第一行给出两个正整数:项目里程碑的数量 N(≤100)和任务总数 M。这里的里程碑从 0 到 N−1 编号。随后 M 行,每行给出一项任务的描述,格式为“任务起始里程碑 任务结束里程碑 工作时长”,三个数字均为非负整数,以空格分隔。 输出格式: 如果整个项目的安排是合理可行的,在一行中输出最早完工时间;否则输出"Impossible"。 输入样例 1: 9 12 0 1 6 0 2 4 0 3 5 1 4 1 2 4 1 3 5 2 5 4 0 4 6 9 4 7 7 5 7 4 6 8 2 7 8 4 输出样例 1: 18 输入样例 2: 4 5 0 1 1 0 2 2 2 1 3 1 3 4 3 2 5 输出样例 2: Impossible
时间: 2023-12-28 21:05:34 浏览: 87
数学建模学习资料 神经网络算法 参考资料-Matlab 共26页.pptx
以下是Python代码实现,可以根据输入的任务关系计算出项目的最早完工时间:
```python
INF = 0x7fffffff
def topo_sort():
res = 0
cnt = 0
q = []
for i in range(n):
if in_deg[i] == 0:
q.append(i)
while q:
u = q.pop(0)
cnt += 1
res = max(res, dist[u])
for v, w in edges[u]:
in_deg[v] -= 1
dist[v] = max(dist[v], dist[u] + w)
if in_deg[v] == 0:
q.append(v)
if cnt != n:
return -1
else:
return res
n, m = map(int, input().split())
in_deg = [0] * n
dist = [-INF] * n
edges = [[] for _ in range(n)]
for i in range(m):
u, v, w = map(int, input().split())
edges[u].append((v, w))
in_deg[v] += 1
print(topo_sort())
```
算法的核心思想是拓扑排序,通过计算任务之间的依赖关系和工作时间,计算出每个任务的最早开始时间。最终,取所有任务中的最大值即为整个项目的最早完工时间。如果存在任务之间的循环依赖,则无法完成整个项目,输出"Impossible"。
阅读全文