gpt4 book ai didi

algorithm - 给定一个加权图和自然数 k 如何找到从节点 s 到 t 的最便宜路径可以被 k 整除?

转载 作者:行者123 更新时间:2023-12-05 04:55:47 25 4
gpt4 key购买 nike

给定一个不包含负循环的加权图 G=(V,E)、一个自然数 k 和两个顶点:s,t。

如何找到从 s 到 t 的最便宜路线,其长度可以除以 k?

最佳答案

准备一个新图 G',顶点为 V × {0, 1, …, n−1} 并且对于 G 中长度为 ℓ 的每个弧 v → w,弧 (v, x) → (w, (x + ℓ) 模 k).然后使用 Dijkstra 算法找到从 (s, 0) 到 (t, 0) 的最短路径。

关于algorithm - 给定一个加权图和自然数 k 如何找到从节点 s 到 t 的最便宜路径可以被 k 整除?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/65217285/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com