【每日一题0911】最短编译耗时

:woman_mage:已知各个python模块编译的耗时和所依赖模块的信息列表info。其中元素的类型是元组,格式为(模块名,编译耗时,依赖模块名称… ),例如(module3,10,module1,module2)表示module3依赖于module1和module2,且自己编译耗时需要10秒。如果没有依赖则对应值为None,所依赖的多个模块会并发执行编译。

请编写一个函数,输入编译信息列表info和目标模块名称target,求出给定的目标模块target编译所需的最短耗时。一旦模块之间存在循环依赖,或者所依赖的模块不存在,则一律返回-1。

示例1
输入:info=[("module1", 10, None), ("module2", 5, None),("module3", 10, "module1", "module2")], target="module3"
输出:20。
解析:已知目标模块module3自己编译耗时10,另外依赖于module1(耗时10)和module2(耗时5),因此所有依赖的编译最短耗时是10。因此module3总计20秒可以编译完毕。

示例2
输入:info=[("module1", 10, "module3"), ("module2", 5, None),("module3", 10, "module1")], target="module3"
输出:-1。
解析:由于目标模块module3依赖于module1,而module1又依赖于module3,因此是循环依赖,所以无法进行编译,返回结果为 -1。

题目难度:中等
题目来源:就业班同学面试真题(略作改动)

def min_cost(info: list, target: str) -> int:
    pass


info1 = [("module1", 10, None), ("module2", 5, None),("module3", 10, "module1", "module2")]
info2 = [("module1", 10, "module3"), ("module2", 5, None),("module3", 10, "module1")]
info3 = [("module1", 10, "module2"), ("module2", 5, "module3"),("module3", 10, "module1")]
info4 = [("module1", 10, None), ("module2", 5, "module3"),("module3", 10, "module1", "module2")]

assert min_cost(info1, "module3") == 20
assert min_cost(info2, "module2") == -1
assert min_cost(info3, "module1") == -1
assert min_cost(info4, "module2") == -1