问图中只有一处变化的所有最短路径

EN

假设我有一个有向图G(V，E)，它的权重为正整数，我需要做的就是找出其中一些边之间的最小距离，nodes.In，这个最小距离路径，我最多只能使用K条反向边。例如，对于此输入：

6(节点)

9(边)

2(正整数K)

10 (找到最小距离所需的边对数)

2 1 2(2的边缘->1，权重为2)

3 2 7(3的边缘->2，权重为7)

4 5 6

1 3 8

1 4 4

5 2 8

5 6 10 (边缘7)

1 5 5(边缘8)

4 2 5(边9)

1 6 1(问题1:使用1条反向边找到从1到>6的最小距离)

3 5 0(问题2:使用0反向边找到与3->5的最小距离)

1 2 0

3 5 1

1 2 1

4 3 1

6 4 0

2 6 2

6 4 1

6 4 2(问题10)

输入的不同部分可以使用边数(9，包含3个数字的前9行)和提出的问题数( 10，边后面的10行)进行分隔。

输出必须是：

15 (问题1的答案:使用1条反向边从1到>6的最小距离是15)

14

9

13

2

12

不可能(这两条边之间没有使用0反向边的路径)

17

24

16

我想过为每个问题和每条边运行Dijkstra，而不是只计算到源的最小距离，使用反向边，并在不使用超过K个反向边的情况下尽可能多地更新值。(标签可能是这样的(节点号，到源的最小距离，使用的反向边).But dijkstra找到从源到所有其他节点的最短路径，我认为这可能对我的instance.Could有点夸张这是不是可以更有效地完成？