CF2128F.Strict Triangle

NOI/NOI+/CTSC

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给定一个无向连通图，包含 $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" 都视为肯定回答。

输入输出样例

输入#1

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

输出#1

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)$ 。

在第二个测试点中，不存在合法的权值分配。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页