CF366D Dima and Trap Graph

Dima 和 Inna 喜欢一起度过时光。问题在于，Seryozha 不太情愿出门，不知为何总待在自己房间。但 Dima 和 Inna 彼此非常相爱，甚至决定铤而走险…… Dima 构建了一个“陷阱图”。他大喊：“嘿 Seryozha，快来看我的炫酷图！”以此吸引室友的兴趣，然后把他推进了第一个点。 陷阱图是一个包含 $n$ 个节点和 $m$ 条边的无向图。对于第 $k$ 条边，Dima 指定了一段整数区间，从 $l_k$ 到 $r_k$（$l_k \le r_k$）。为逃出陷阱图，Seryozha 需要在开始移动前选择一个整数（记为 $x$）。随后 Seryozha 必须选择一条路径，从编号为 $1$ 的起点走到编号为 $n$ 的终点。在此过程中，只有当 $l_k \le x \le r_k$ 时，Seryozha 才能沿第 $k$ 条边移动。 Seryozha 是一位数学家。他将从第 $1$ 个节点到第 $n$ 个节点的一条路径的“忠诚度”定义为满足条件的整数 $x$ 的个数——即如果初始选择这些 $x$，他能够按该路径顺利通过。请你帮助 Seryozha 找到一条忠诚度最大的路径，好让他尽快返回房间！

输入的第一行包含两个整数 $n$ 和 $m$，满足 $2 \le n \le 10^3, 0 \le m \le 3 \cdot 10^3$。接下来 $m$ 行每行描述一条边，每行包含四个整数 $a_k, b_k, l_k, r_k$，满足 $1 \le a_k, b_k \le n, 1 \le l_k \le r_k \le 10^6$。这些数字表示第 $k$ 条边连接节点 $a_k$ 和 $b_k$，并关联整数区间 $[l_k, r_k]$。 注意，图中可能存在自环或重边。

输出一行，表示从第一个节点到第 $n$ 个节点的所有路径中的最大忠诚度。如果不存在这样的路径或最大忠诚度为 $0$，则输出一行 “Nice work, Dima!”（不含引号）。

第一个样例的解释： 总共有两种方式可以从节点 1 走到节点 4：首先必须沿边 1-2（区间 $[1, 10]$），然后走到 2-4 的某一条边。 其中一条边区间为 $[3, 5]$，即可通过 $x=3,4,5$，此路径忠诚度为 $3$。 另一条为 $[2,7]$，可以通过 $x=2,3,4,5,6,7$，此路径忠诚度为 $6$，这是答案。 边 1-2 对答案没有限制，因为它的区间包含了后续每条边的区间。 由 ChatGPT 5 翻译