【BZOJ4152】The Captain（最短路）

题面

BZOJ

Description

给定平面上的n个点，定义(x1,y1)到(x2,y2)的费用为min(|x1-x2|,|y1-y2|)，求从1号点走到n号点的最小费用。

Input

第一行包含一个正整数n(2<=n<=200000)，表示点数。

接下来n行，每行包含两个整数x[i],yi，依次表示每个点的坐标。

Output

一个整数，即最小费用。

Sample Input

2 2

1 1

4 5

7 1

6 7

Sample Output

题解

分别按照\(x,y\)排序

只有相邻的才会连边（为什么？因为连接更远的点一定可以拆成走两次）

直接跑\(SPFA\)然后我就\(TLE\)了

换成\(Dijkstra\)美滋滋

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<set>

#include<map>

#include<vector>

#include<queue>

using namespace std;

#define ll long long

#define RG register

#define MAX 222222

inline int read()

{

    RG int x=0,t=1;RG char ch=getchar();

    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

    if(ch=='-')t=-1,ch=getchar();

    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

    return x*t;

}

int n;

struct Line{int v,next,w;}e[MAX<<2];

int h[MAX],cnt=1;

inline void Add(int u,int v,int w){e[cnt]=(Line){v,h[u],w};h[u]=cnt++;}

struct Node{int x,y,id;}p[MAX];

bool cmp1(Node a,Node b){return a.x<b.x;}

bool cmp2(Node a,Node b){return a.y<b.y;}

int dis[MAX];

bool vis[MAX];

priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >Q;

void Dijkstra()

{

	Q.push(make_pair(0,1));

	pair<int,int> u;

	while(!Q.empty())

	{

		u=Q.top();Q.pop();

		if(vis[u.second])continue;

		vis[u.second]=true;

		dis[u.second]=u.first;

		for(int i=h[u.second];i;i=e[i].next)

		{

			int v=e[i].v;

			if(vis[v])continue;

			Q.push(make_pair(u.first+e[i].w,v));

		}

	}

}

int main()

{

	n=read();

	for(int i=1;i<=n;++i)p[i].x=read(),p[i].y=read(),p[i].id=i;

	sort(&p[1],&p[n+1],cmp1);

	for(int i=1;i<n;++i)

	{

		Add(p[i].id,p[i+1].id,abs(p[i].x-p[i+1].x));

		Add(p[i+1].id,p[i].id,abs(p[i].x-p[i+1].x));

	}

	sort(&p[1],&p[n+1],cmp2);

	for(int i=1;i<n;++i)

	{

		Add(p[i].id,p[i+1].id,abs(p[i].y-p[i+1].y));

		Add(p[i+1].id,p[i].id,abs(p[i].y-p[i+1].y));

	}

	Dijkstra();

	printf("%d\n",dis[n]);

	return 0;

}

巴特西

【BZOJ4152】The Captain（最短路）

【BZOJ4152】The Captain（最短路）

题面

Description

Input

Output

Sample Input

Sample Output

题解

最新文章

热门文章