BZOJ 4152（AMPPZ 2014）The Captain（最短路）

发表于 |
字数统计: 491字 | 阅读时长 ≈ 3min

【AMPPZ2014】船长

问题描述

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

输入格式

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

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

输出格式

一个整数，即最小费用。

样例输入

5

2 2

1 1

4 5

7 1

6 7

样例输出

2

注意到这个距离的定义，直接先按x排序，相邻点连边，然后按y排序，相邻点连边，然后跑Dijkstra就行了。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#define N 200005
#define M 2000005
#define ll long long
using namespace std;
typedef pair<ll,ll> par; 
struct node{ll x,y,id;}P[N];
ll n,TOT,LA[N],NE[M],EN[M],LE[M],dis[N];
priority_queue<par>Q;
bool cmp1(node a,node b)
{return a.x<b.x;}
bool cmp2(node a,node b)
{return a.y<b.y;}
void ADD(ll x,ll y,ll z)
{
	TOT++;
	EN[TOT]=y;
	LE[TOT]=z;
	NE[TOT]=LA[x];
	LA[x]=TOT;
}
void Link(ll x,ll y,ll z){ADD(x,y,z);ADD(y,x,z);}
void Dijkstra()
{
	fill(dis,dis+n+1,1e18);
	dis[1]=0;Q.push(par(0,1));
	while(Q.size())
	{
		par tmp=Q.top();
		Q.pop();
		if(dis[tmp.second]!=-tmp.first)continue;
		for(int i=LA[tmp.second];i;i=NE[i])
		{
			int y=EN[i];
			if(dis[y]>LE[i]-tmp.first)
			{
				dis[y]=LE[i]-tmp.first;
				Q.push(par(-dis[y],y));
			}
		}
	}
}
int main()
{
	ll i;
	scanf("%lld",&n);
	for(i=1;i<=n;i++)scanf("%lld%lld",&P[i].x,&P[i].y),P[i].id=i;
	sort(P+1,P+n+1,cmp1);
	for(i=2;i<=n;i++)Link(P[i].id,P[i-1].id,P[i].x-P[i-1].x);
	sort(P+1,P+n+1,cmp2);
	for(i=2;i<=n;i++)Link(P[i].id,P[i-1].id,P[i].y-P[i-1].y);
	Dijkstra();printf("%lld",dis[n]);
}