← 返回题目列表

Codeforces · 2128/F

F. 严格三角形

中文机器翻译题面 查看原题

给您一个无向连通图,其中包含 $$$n$$$ 节点和 $$$m$$$ 边。第 $$$i$$$ 条边的权重 $$$w_i$$$ 尚未确定,必须是 $$$l_i$$$ 和 $$$r_i$$$ 之间的实数。

给你一个节点$$$k$$$。确定是否存在有效的权重 $$$(w_1, \ldots, w_m)$$$ 分配,使得:

  • $$$l_i \leq w_i \leq r_i$$$ 对于所有 $$$i$$$,并且
  • $$$\mathrm{dist}_w(1, n) \neq \mathrm{dist}_w(1, k) + \mathrm{dist}_w(k, n)$$$$$$^{\text{*}}$$$。

$$$^{\text{*}}$$$给定权重 $$$w$$$ 的分配,$$$\mathrm{dist}_w(u, v)$$$ 是 $$$w_{e_1} + w_{e_2} + \ldots + w_{e_p}$$$ 在所有 $$$p$$$ 边序列上的最小值$$$(e_1, e_2, \ldots, e_p)$$$ 形成从 $$$u$$$ 到 $$$v$$$ 的路径。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10\,000$$$)。测试用例的描述如下。

每个测试用例的第一行包含三个整数 $$$n$$$、$$$m$$$ 和 $$$k$$$ ($$$4 \le n \le 200\,000$$$, $$$n-1 \le m \le 200\,000$$$, $$$2 \le k \le n - 1$$$) — 节点数,边的数量和节点 $$$k$$$。

以下 $$$m$$$ 行中的第 $$$i$$$ 行包含四个整数 $$$u_i$$$、$$$v_i$$$、$$$l_i$$$ 和 $$$r_i$$$ ($$$1 \le u_i, v_i \le n$$$, $$$u_i \ne v_i$$$, $$$1 \le l_i \le r_i \le 10^9$$$),表示 $$$u_i$$$ 和 $$$v_i$$$ 之间的边,其权重必须在 $$$l_i$$$ 和 $$$r_i$$$ 之间(含)。输入中没有边出现多次。

保证:

  • 所有测试用例的 $$$n$$$ 总和不超过 $$$200\,000$$$
  • 所有测试用例的 $$$m$$$ 总和不超过 $$$200\,000$$$

输出

打印 是 如果存在有效的权重分配并且 NO 否则。

您可以在任何情况下输出答案(大写或小写)。例如,字符串“是", "是", "是“,和”是”将被视为积极响应。

示例

输入
复制

7
4 4 2
1 2 10 20
2 3 10 30
1 3 49 90
4 3 1 1000
4 4 2
1 2 10 20
2 3 10 30
1 3 50 90
4 3 1 1000
5 7 3
1 2 1 100000
1 4 10 100
2 3 1 100000
3 4 1 100000
2 5 2 100000
3 5 1 1
4 5 1 31
5 7 3
1 2 1 100000
1 4 100000 100000
2 3 1 1
3 4 1 100000
2 5 2 100000
3 5 1 1
4 5 1 31
5 5 3
1 2 1 42
2 4 1 42
4 5 1 42
1 3 1 1
3 5 1 42
5 5 3
1 2 1 42
2 4 1 42
4 5 1 42
1 3 1 1
3 5 1 1
5 5 3
1 2 1 42
2 4 1 42
4 5 1 42
1 3 1 1
3 5 2 2

输出
复制

YES
NO
YES
YES
YES
NO
NO

注意

在第一个测试用例中, $$$w = (20, 30, 49, 21)$$$ 是有效的权重分配,因为 $$$\mathrm{dist}_w(1, 4) = 70 \neq 71 = \mathrm{dist}_w(1, 2) + \mathrm{dist}_w(2, 4)$$$。

在第二个测试用例中,没有有效的权重分配。