加权有向图最短路径算法：限制边数的路径查找

问题描述: 给定一个加权有向图，可能权值存在负数，找到从给定源到给定目的地的成本最低的路径，路径可能重复经过同一个点，且该路径恰好有m条边。

输入格式: 第一行包含三个正整数，分别表示节点数量n，边的数量e，路径的边数限制m。

接下来e行，每行包含三个整数u、v、w，表示一条有向边从u指向v，权值为w。

最后一行包含两个整数s、t，表示需要找到从s到t恰好有m条边的最短路径。

输出格式: 输出一个整数，表示从s到t恰好有m条边的最短路径长度。如果不存在这样的路径，则输出2147483647。

输入样例1: 4 4 2 1 2 1 2 3 2 3 4 3 4 1 -4 1 3 输出样例1: 2147483647

输入样例2: 4 4 2 1 2 1 2 3 2 3 4 3 4 1 -4 1 4 输出样例2: -1

算法实现: 可以使用动态规划算法来解决这个问题。定义dp[i][j]表示从源点到节点i，经过j条边的最短路径长度。对于每个节点i，枚举其所有相邻的节点k，计算从源点到节点k，经过j-1条边的最短路径长度，再加上边(k,i)的权值，更新dp[i][j]的值。

示例代码:

import sys

def shortest_path(n, e, m, edges, source, destination):
    dp = [[sys.maxsize] * (m + 1) for _ in range(n + 1)]
    dp[source][0] = 0
    for j in range(1, m + 1):
        for u in range(1, n + 1):
            for k in range(1, n + 1):
                if (u, k) in edges:
                    w = edges[(u, k)]
                    dp[u][j] = min(dp[u][j], dp[k][j - 1] + w)
    if dp[destination][m] == sys.maxsize:
        return 2147483647
    else:
        return dp[destination][m]

if __name__ == '__main__':
    n, e, m = map(int, input().split())
    edges = {}
    for _ in range(e):
        u, v, w = map(int, input().split())
        edges[(u, v)] = w
    source, destination = map(int, input().split())
    result = shortest_path(n, e, m, edges, source, destination)
    print(result)

测试用例: 上面的示例代码已经包含了两个测试用例。可以根据需要添加更多测试用例进行测试。

注意: 本算法的时间复杂度为O(n^2 * m)，空间复杂度为O(n * m)。如果图中存在负权环，则算法可能无法找到最短路径。