algorithm - 如何证明无向加权图中的最长路径是 NP 完全的？

Question

我知道要证明任何问题都是 NP 完全的，你必须证明

1. 它在NP中。

2. 这是NP难的。

我知道如何证明无向无权图中的最长路径，但对于加权图，我完全不知道；如何证明它 NP-hard 和 NP。

实际上给定的问题说“证明问题'找到给定的无向加权图具有包含总权重> = K的最长路径'”

令 G = (V, E) 为无向加权图，K 为正整数。