给出了一个加权的无方向图，检查在顶点1和n之间是否存在权重k的路径。
看起来像一个NP问题，但要求我在2秒内检查它，K为<= 10 ^ 18。我们可以根据需要使用每条道路多次。将不胜感激。
N和M非常小（<= 50），因此我考虑将dp用于权重最大为k的路径。N，M，K是整数，边缘的权重<10 ^ 4。该图可能未连接。很遗憾，此问题来自代码部队培训，该语句不是英语，因此在附加该语句时不会有任何用处。
有一个国家有n个城市，城市的编号从1到n，所有道路均通向。每条道路连接两个城市。
沃克先生真的很喜欢散步。沿任何方向向任何方向行驶都需要w（i）分钟。沃克先生不住在城市，一到达一个城市，他便立即去另一个城市。
沃克先生从排名第一的城市开始，希望在整整K分钟内到达第n个城市。您需要检查是否可行。
输入-第一行包含两个整数n，m（1 ??? n，？m ??? 50）。接下来的m行描述道路a（i）-起点，b（i）-终点，d（i）-沿着这条路行驶所需的时间（1 ??? ai，？bi ??? n; 1 ??? di ??? 10 ^ 4）。
最后一行包含数字k-沃克先生希望其路径采用的时间（1 ??? t ??? 10 ^ 18）。
如果可以的话，打印是可能的；如果沃克先生不能在准确的k分钟内到达第n个城市，则不可能。
请注意，我们可以对加权邻接矩阵进行矩阵求幂来计算长度为k的路径的所有可能的路径权重。这需要O(n 3 log(k))时间。假设没有负权重，矩阵M k中的所有条目都大于或等于M k-1中的条目。
现在，如果存在权重为 K的路径，我们可以假设它必须具有某个有限长度k'。我们可以使用矩阵求幂中最左上角的元素对k'进行二分搜索。由此得出的结果要么是一个有效的k' ，它在左上角给出了K ，这意味着我们完成了，我们找到了解决方案，要么二分搜索告诉我们不存在这样的k'，因此我们可以消除左上角。
你对矩阵中的每个位置都这样做，然后要么将它们全部消除，要么找到解决方案。总复杂度为O(n 5 log(k'))，这不是很好，但它是一种算法。