本题数据非常弱——据不少人所说,在本题数据中,起点 S 到终点 T 的最短路径至多只有一条。(即 FrenkiedeJong21 题解中提到的“不靠谱的过题办法”)
另外,在本题的限制下,起点 S 到终点 T 的最短路径的数量可以达到指数级别。然而,包括 Cyhlnj 和 GNAQ 的题解在内的不少代码却直接使用了 long long
存储最短路径的数量,这显然是错误的。正确的做法是像 FrenkiedeJong21 题解那样,将最短路径的数量对大质数取模。(在本题的限制下,几乎不可能构造出在大质数模意义下相等的情况)
以下的剪贴板链接包含两份 Hack 数据的 generator 及构造说明:
洛谷 P4061 Hack 数据
此处附上题解代码在 Hack 数据下的运行情况:
测试代码 | #1 | #2 |
---|
Cyhlnj 题解中的两份代码 | WA | WA |
GNAQ 题解代码 | AC | WA |
FrenkiedeJong21 题解中“不靠谱的过题办法” | WA | WA |
FrenkiedeJong21 题解中后两份代码 | AC | AC |
个人不清楚添加 Hack 数据会不会出现版权问题,若不会则请求管理员将这两组 Hack 数据加入该题数据。
另外,Cyhlnj 和 GNAQ 的题解请管理员决定是否撤下。