寻寻觅觅,不知错在哪?呜呜~~~
查看原帖
寻寻觅觅,不知错在哪?呜呜~~~
376452
colin_lord楼主2021/9/9 17:14
#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;

这句就可以过 实属不明白原因,求救!!!

2021/9/9 17:14
加载中...