#P2830. 第2题-简单路径

    ID: 2462 Tried: 13 Accepted: 2 Difficulty: 6 所属公司 : 阿里 时间 :2025年4月12日-阿里淘天(开发岗)
      算法标签>拓扑排序dfs动态规划

第2题-简单路径

题目内容

TkTk 有一个由nn个节点mm条有向边组成的,节点编号为11~nn的有向无环图,编号i的节点有一股强度为aia_i的初始能量。 每过一个单位时间,所有节点的能量都会下降kk(能量不会下降为负值,即如果有节点能量小于k时只会下降至00),TkTk经过一条边需要花费一个单位时间。

定义每个节点的不确定性,是TkTk从此节点出发、到能到达的所有节点,到达时的最大能量减去能到达的所有节点,到达时的最小能量(无需保证最大能量节点与最小能量节点在同个简单路径)。你需要求出每个节点的不稳定性。