CF2128F Strict Triangle

给定一个无向连通图，包含 $n$ 个节点和 $m$ 条边。第 $i$ 条边的权值 $w_i$ 尚未确定，必须是 $l_i$ 到 $r_i$ 之间的实数。 给定一个节点 $k$，请判断是否存在一种合法的权值分配 $(w_1, \ldots, w_m)$，使得： - 对所有 $i$，有 $l_i \leq w_i \leq r_i$； - $\mathrm{dist}_w(1, n) \neq \mathrm{dist}_w(1, k) + \mathrm{dist}_w(k, n)$。 其中，给定一组权值 $w$，$\mathrm{dist}_w(u, v)$ 表示所有从 $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$ 行，每行包含四个整数 $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$。

如果存在一种合法的权值分配，输出 YES，否则输出 NO。 输出不区分大小写，例如 "yEs"、"yes"、"Yes"、"YES" 都视为肯定回答。

在第一个测试点中，$w = (20, 30, 49, 21)$ 是一种合法的权值分配，因为 $\mathrm{dist}_w(1, 4) = 70 \neq 71 = \mathrm{dist}_w(1, 2) + \mathrm{dist}_w(2, 4)$。 在第二个测试点中，不存在合法的权值分配。 由 ChatGPT 4.1 翻译