Krydom: 暁の水平线に胜利を刻むのです

ソロモンの悪夢、見せてあげる!

@krydom1年前

12/6
20:36
dijkstra

[bzoj 4152] [AMPPZ2014]The Captain

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

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

♦♦♦♦♦♦   Input   ♦♦♦♦♦♦

第一行包含一个正整数n(2<=n<=200000),表示点数。
接下来n行,每行包含两个整数x[i],y[i](0<=x[i],y[i]<=10^9),依次表示每个点的坐标。

♦♦♦♦♦♦   Output   ♦♦♦♦♦♦

一个整数,即最小费用。

♦♦♦♦♦♦   Sample Input   ♦♦♦♦♦♦

5
2 2
1 1
4 5
7 1
6 7

♦♦♦♦♦♦   Sample Output   ♦♦♦♦♦♦

2

♦♦♦♦♦♦   Hint   ♦♦♦♦♦♦

♦♦♦♦♦♦   题解  ♦♦♦♦♦♦

很显然一个点之后它周围的点连的边有影响,所以分别按照x,y轴排序后连边,跑一遍最短路就好了

听说本题卡spfa

 

[bzoj 4152] [AMPPZ2014]The Captain