#include<iostream>
#include<bits/stdc++.h>
using namespace std;
const int N = 100055 , M = 200080 , inf = (1 << 30) - 1;
struct edge{
int f , t , w;
}e[N << 2];
struct node{
int x , y , id;
bool operator <(const node &a)const{
return x < a.x;
}
}nd[N];
int n , m , cnt;
int h[M] , dis[M];
int s , t;
bool vis[M];
int dist(int x , int y){return 2 * (abs(nd[x].x - nd[y].x) + abs(nd[x].y - nd[y].y));}
bool cmp(node x , node y)
{
return x.y < y.y;
}
int rd()
{
int al = 0 , f = 1;char b = getchar();
while(!isdigit(b)){ if(b == '-') f = -1; b = getchar();}
while(isdigit(b)){al = al * 10 + b - '0';b = getchar();}
return al * f;
}
void spfa()
{
queue<int> q;
for(int i = 1;i <= m * 2;i ++){
dis[i] = inf;
}
q.push(s);
dis[s] = 0 , vis[s] = 1;
while(q.size()){
int u = q.front();
q.pop();
vis[u] = 0;
for(int i = h[u]; i ;i = e[i].f){
int v = e[i].t;
if(dis[v] > dis[u] + e[i].w){
dis[v] = dis[u] + e[i].w;
if(!vis[v]){
vis[v] = 1;
q.push(v);
}
}
}
}
}
void add(int u , int v , int w)
{
e[++ cnt].f = h[u] , e[cnt].t = v;
e[cnt].w = w; h[u] = cnt;
}
int main()
{
n = rd() , m = rd();
s = m + 1 , t = m + 2;
m += 2;
for(int i = 1;i <= m;i ++){
nd[i].x = rd() , nd[i].y = rd();
nd[i].id = i;
}
sort(nd + 1 , nd + m + 1);
for(int i = 1;i < m;i ++){
if(nd[i].x == nd[i + 1].x){
int u = nd[i].id , v = nd[i + 1].id , w = dist(i , i + 1);
cout << w << endl;add(u , v , w) , add(v , u , w);
}
}
sort(nd + 1 , nd + m + 1 , cmp);
for(int i = 1;i < m;i ++){
if(nd[i].y == nd[i + 1].y){
int u = nd[i].id + m , v = nd[i + 1].id + m , w = dist(i , i + 1);
cout << w << endl;
add(u , v , w) , add(v , u , w);
}
}
for(int i = 1;i <= m - 2;i ++){
add(i , i + m , 1) , add(i + m , i , 1);
}
add(m - 1 , 2 * m - 1 , 0); add(2 * m - 1 , m - 1 , 0);
add(m , 2 * m , 0); add(2 * m , m , 0);
spfa();
if(dis[t] == inf){
cout << -1 << endl;
}
else cout << dis[t] << endl;
}
以上代码是错误代码,啊啊啊~ 然后我们在重载node运算符的时候加上
if(x != a.x) return x < a.x;
return y < a.y;
这句就可以过 实属不明白原因,求救!!!