怎么说呢，相信很多考过竞赛的同学都会在平时的练习/考试中遭遇过100分但没有AC的情况，结果一看评测结果：subtask的数据点没过！

这时候就是遇到hack数据了，如果被这类数据卡住，说明你的代码可能还存在一些潜在的BUG，需要你细心分析。

在这里猫猫就以自己的一道题目来简要说说hack数据的构造有什么思路：

【本题来源：比特山】

16: 猫猫和狐狸在迷宫里的赛跑~ 较难

作者/来源：白风（题目提供）

题目背景

（天洛是狐狸、白风是猫猫）

为了整治一下天洛这只懒狐狸不愿意动的习惯，猫猫不由分说的把天洛扔到了一个迷宫里：“嗷呜！放我回去！！”

面对着天洛的哀嚎，白风笑着晃了晃手中的杯子：“看看这是什么w~”

“这是……暴打柠檬茶？！”看着朝自己扑过来的屑狐狸，猫猫只是轻轻一躲便是闪了过去：“想喝吧？w来追我呀~追到我就给你w”

“嗷呜！~”

题目描述

现在狐狸和猫猫身处一个迷宫之中，记性不好的猫只能记得眼前的分支中最短的一条路径，比如对于节点A、B、C，若从A到B的距离短于从A到C的距离，猫就会选择从A节点往B节点移动。

狐狸有地图，但是猫猫没有地图。

狐狸拿到地图之后，可以选择路线穿过一个个房间，最终堵住猫猫的去路，拿到他爪中的柠檬茶。

现在请你帮天洛规划路线。

接矩阵第1行第2列的意思是：从输入顺序的第一个节点（很显然就是1）到输入顺序的第二个节点（就是2）的距离】

【比如输入#1中邻接矩阵第1行第2列的意思是：从输入顺序的第一个节点(很显然就是1)到输入顺序的第二个节点(就是2)的距离为1】

1 2 3 4 5
0 1 2 -1 -1
1 0 3 -1 2
2 3 0 1 -1
-1 -1 1 0 1
-1 2 -1 1 0
1 2 3 4 5
0 1 2 -1 -1
1 0 3 -1 2
2 3 0 1 -1
-1 -1 1 0 1
-1 2 -1 1 0
1 2 3 4 5
0 1 2 -1 -1
1 0 3 -1 2
2 3 0 1 -1
-1 -1 1 0 1
-1 2 -1 1 0

上面的图对应的样子如下图所示：

若1为起点，4为终点，那么红色就是狐狸追的路径，绿色是猫猫逃跑的路径

红色路径比绿色路径短，就成功抓到了。

而你要实现的功能就是：找出所有可以到达出口的路线中总体最短的路线，在猫猫到达出口之前，抢先一步到达出口，以此来堵住猫猫的去路。

注意，若同时到达，由于猫猫比较灵活，此时狐狸还是追不上猫猫的，这种情况下也为无解

加油！狐狸能不能喝上柠檬茶就看你了！

交互格式说明

交互格式样例

5
1 2 3 4 5
0 1 2 -1 -1
1 0 3 -1 2
2 3 0 1 -1
-1 -1 1 0 1
-1 2 -1 1 0
1 4
5
1 2 3 4 5
0 1 2 -1 -1
1 0 3 -1 2
2 3 0 1 -1
-1 -1 1 0 1
-1 2 -1 1 0
1 4
5
1 2 3 4 5
0 1 2 -1 -1
1 0 3 -1 2
2 3 0 1 -1
-1 -1 1 0 1
-1 2 -1 1 0
1 4

3
1
3
4
3
1
3
4
3
1
3
4

5
1 2 3 4 5
0 1 2 -1 -1
1 0 3 -1 2
2 3 0 1 -1
-1 -1 1 0 1
-1 2 -1 1 0
1 5
5
1 2 3 4 5
0 1 2 -1 -1
1 0 3 -1 2
2 3 0 1 -1
-1 -1 1 0 1
-1 2 -1 1 0
1 5
5
1 2 3 4 5
0 1 2 -1 -1
1 0 3 -1 2
2 3 0 1 -1
-1 -1 1 0 1
-1 2 -1 1 0
1 5

-1
-1
-1

提示

数据保证，最短路径只有一个

同时，猫猫为了让狐狸多跑几圈，特意设计了几个环，允许狐狸在一个房间里兜圈子

注意，此题中各个节点之间的距离一定为非负整数

如果存在相同距离的点，那么猫猫和狐狸都会选择未探索节点中节点编号最小的那条路线，比如如果有两条距离相同的路线：

路线A：1→2→5→7→9→…

路线B：1→2→3→7→12→…

则最终选择为路线B

若存在猫猫无法到达终点的情况，输出依然按照有解情况进行

同理，若存在狐狸无法到达终点的情况，输出依然按照无解情况进行

纵使迷宫千奇百怪，真相永远只有一个……

 猫猫の解读

认真读一下题目，基本上思路其实就有了。

猫猫选择的很明显是一种“贪心”的思想，也就是所谓的贪心算法。

而狐狸则是选择了最短路径，我们可以使用Dijkstra最短路径算法得出答案。

是不是感觉这一题很简单？但是……小心细节w

猫猫在一番折腾后，一共提交了5组数据点：

第一组（正常数据，用于测试你的程序是否能按要求完成任务）：

race1.in

5
1 4 2 6 7
0 1 1 -1 3
1 0 1 1 1
1 1 0 2 -1
-1 1 2 0 1
3 1 -1 1 0
1 7
5
1 4 2 6 7
0 1 1 -1 3
1 0 1 1 1
1 1 0 2 -1
-1 1 2 0 1
3 1 -1 1 0
1 7
5
1 4 2 6 7
0 1 1 -1 3
1 0 1 1 1
1 1 0 2 -1
-1 1 2 0 1
3 1 -1 1 0
1 7

race1.out

2
1
4
7
2
1
4
7
2
1
4
7

平平无奇，并没有什么特别的。

第二组（正常数据，但是相对节点数较多，作为大数据测试）：

race2.in

race2.out

1
1
100
1
1
100
1
1
100

这个数据相对大一点，但其实也问题不大【只要你的程序没写太拉也能过】

不过，下面几组数据可就没这么简单了w~

第三组（hack数据，出现自环情况，可以在同一个节点兜圈子，如果使用贪心算法可能出现最后程序无法结束导致TLE）：

race3.in

12
1 2 3 4 5 6 7 8 9 10 11 12
1 3 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
3 1 1 2 3 -1 -1 -1 -1 -1 -1 -1
-1 1 1 1 -1 95 17 -1 -1 -1 -1 -1
-1 2 1 1 2 3 4 5 -1 -1 -1 -1
-1 3 -1 2 1 -1 2 99 -1 -1 -1 -1
-1 -1 95 3 -1 1 -1 -1 96 15 -1 -1
-1 -1 17 4 2 -1 1 1 21 5 43 -1
-1 -1 -1 5 99 -1 1 1 -1 27 99 -1
-1 -1 -1 -1 -1 96 21 -1 1 1 -1 -1
-1 -1 -1 -1 -1 15 5 27 1 1 1 3
-1 -1 -1 -1 -1 -1 43 99 -1 1 1 -1
-1 -1 -1 -1 -1 -1 -1 -1 -1 3 -1 1
1 12
12
1 2 3 4 5 6 7 8 9 10 11 12
1 3 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
3 1 1 2 3 -1 -1 -1 -1 -1 -1 -1
-1 1 1 1 -1 95 17 -1 -1 -1 -1 -1
-1 2 1 1 2 3 4 5 -1 -1 -1 -1
-1 3 -1 2 1 -1 2 99 -1 -1 -1 -1
-1 -1 95 3 -1 1 -1 -1 96 15 -1 -1
-1 -1 17 4 2 -1 1 1 21 5 43 -1
-1 -1 -1 5 99 -1 1 1 -1 27 99 -1
-1 -1 -1 -1 -1 96 21 -1 1 1 -1 -1
-1 -1 -1 -1 -1 15 5 27 1 1 1 3
-1 -1 -1 -1 -1 -1 43 99 -1 1 1 -1
-1 -1 -1 -1 -1 -1 -1 -1 -1 3 -1 1
1 12
12
1 2 3 4 5 6 7 8 9 10 11 12
1 3 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
3 1 1 2 3 -1 -1 -1 -1 -1 -1 -1
-1 1 1 1 -1 95 17 -1 -1 -1 -1 -1
-1 2 1 1 2 3 4 5 -1 -1 -1 -1
-1 3 -1 2 1 -1 2 99 -1 -1 -1 -1
-1 -1 95 3 -1 1 -1 -1 96 15 -1 -1
-1 -1 17 4 2 -1 1 1 21 5 43 -1
-1 -1 -1 5 99 -1 1 1 -1 27 99 -1
-1 -1 -1 -1 -1 96 21 -1 1 1 -1 -1
-1 -1 -1 -1 -1 15 5 27 1 1 1 3
-1 -1 -1 -1 -1 -1 43 99 -1 1 1 -1
-1 -1 -1 -1 -1 -1 -1 -1 -1 3 -1 1
1 12

race3.out

16
1
2
5
7
10
12
16
1
2
5
7
10
12
16
1
2
5
7
10
12

这组数据就是检查你读题到底有没有读完了，如果没有读完没看到最后的提示……哼哼，这个点可能分就没了。

不过相信应该大多数人不至于在这个点上被卡住……（bushi）

第四组（hack数据，在编号映射和数据大小上分别针对int和long long的存储范围进行hack，如果没有注意到题目中没有给出数据范围这个点很容易被忽视）

race4.in

3
1 3 5
2147483648 2147483649 2147483650
2147483647 4200000000 4100000000
4611686018427387904 4611686018427387905 2147483648
1 5
3
1 3 5
2147483648 2147483649 2147483650
2147483647 4200000000 4100000000
4611686018427387904 4611686018427387905 2147483648
1 5
3
1 3 5
2147483648 2147483649 2147483650
2147483647 4200000000 4100000000
4611686018427387904 4611686018427387905 2147483648
1 5

race4.out

2147483650
1
5
2147483650
1
5
2147483650
1
5

这组数据说实话属实有点***钻，主要是谁会想到还会对long long这种类型进行hack呢……

【当然比赛场上一般不会选择这样hack，毕竟比赛的时候谁都不想写高精度……xwx】

第五组（hack数据，对编号映射针对long long进行hack，而且给出的是单节点图，很容易被人忽视）

race5.in

1
9223372036854775807
18446744073709551617
9223372036854775807 9223372036854775807
1
9223372036854775807
18446744073709551617
9223372036854775807 9223372036854775807
1
9223372036854775807
18446744073709551617
9223372036854775807 9223372036854775807

race5.out

-1
-1
-1

说实话，这组数据真的很容易被忽视，因为他整张图只有一个节点……

所以说细节决定成败，如果真的没注意的话很容易被hack掉……

总结

读到这里有人就想问了，那你是怎么想到这种hack数据呢？

emm……首先，在假设你对题目所用的算法了解的话，你需要做的就是理解题目中隐藏的信息。

就比如本题中题目中有一句：“注意，若同时到达，由于猫猫比较灵活，此时狐狸还是追不上猫猫的，这种情况下也为无解”

这句话作用是什么？

这不是明摆着告诉你有数据点能卡这个嘛……

说白了，所谓的hack数据只是为了保证你的代码具有能真正解决问题的能力，而不是会被一些特殊数据给hack掉。

所谓的“hack数据”，何尝不是对你题目理解能力的考察吗？

只要题目读透了，不读错题目【有时候猫猫会想当然结果最后爆0】

区区hack数据能奈我何？

【这里还有一些有意思的聊天记录.jpg】

⌬白风-Cryflmind⌬ 2023/7/27 10:40:57
说起来上面那个图论题我用map映射一下节点编号会不会方便处理一些？

Mathematica 2023/7/27 10:41:52
我用数组映射的

⌬白风-Cryflmind⌬ 2023/7/27 10:42:14
owo桶喵？

Mathematica 2023/7/27 10:42:23

Mathematica 2023/7/27 10:42:50
话说编号可以hack我

⌬白风-Cryflmind⌬ 2023/7/27 10:43:12
w编号写大点这样写就给你写RE了

Mathematica 2023/7/27 10:43:20
哈哈哈哈哈对

Mathematica 2023/7/27 10:44:14
可以加强数据

⌬白风-Cryflmind⌬ 2023/7/27 10:44:23
是的w

⌬白风-Cryflmind⌬ 2023/7/27 10:45:08
回来洛谷原题我再扔个Hack上去

⌬白风-Cryflmind⌬ 2023/7/27 10:46:30
幸好这个题不在codeforces上.jpg

Mathematica 2023/7/27 10:47:05
笑死

 后记

顺带一提，其实这个题目里面还能提出新的hack数据，我提交的数据集其实并不是完美的。

所以，或许你可以试试自己构造一组hack？

给你个提示吧，我前面给的所有图都是个连通图w~

多动手，多思考，自然就水到渠成了喵~