样例可以过qaq
by 廖浩聃 @ 2022-08-12 15:57:36
@[廖浩聃](/user/555106) 链式前向星下标存的是第几条边,所以要开大一点,还有不用找出所有边,找最短边就行了,还有你初始化的是-1,所以应该push(1 ,0 ,-1)。
```cpp
sort(a ,a + n + 1 ,cmp);
for(int i = 1;i <= n;i++) {
add(a[i].id ,a[i + 1].id ,abs(a[i].x - a[i + 1].x));
add(a[i + 1].id ,a[i].id ,abs(a[i].x - a[i + 1].x));
}
sort(a ,a + n + 1 ,cmp1);
for(int i = 1;i <= n;i++) {
add(a[i].id ,a[i + 1].id ,abs(a[i].y - a[i + 1].y));
add(a[i + 1].id ,a[i].id ,abs(a[i].y - a[i + 1].y));
}
//排序之后相邻两个点距离最短,将点的横纵坐标都排序一遍,一定会有最短路
```
by Lien @ 2022-08-12 15:57:40
@[廖浩聃](/user/555106) 如果找出所有边,多了个n^2,大概率会TLE。
by Lien @ 2022-08-12 16:01:29
@[Lien](/user/711752) 那大概应该开多大?
~~现在RE7个点~~
by 廖浩聃 @ 2022-08-12 16:01:30
@[Lien](/user/711752) ```sort(a ,a + n + 1 ,cmp1);```
虽然但是,哥您这sort……
by 廖浩聃 @ 2022-08-12 16:02:45
@[廖浩聃](/user/555106) 我开的2000005。
by Lien @ 2022-08-12 16:03:32
@[廖浩聃](/user/555106) 记下原本点的序号(a[i].id)就行了。
by Lien @ 2022-08-12 16:04:38
@[Lien](/user/711752) 私吧ovo
by 廖浩聃 @ 2022-08-12 16:05:12
@[Lien](/user/711752) 开这么大不会MLE咩,我开200005都爆炸了
by bxssss @ 2022-08-12 16:05:25
@[bxssss](/user/670842) 二维当然会M。。
by 廖浩聃 @ 2022-08-12 16:06:10