首页 > 代码库 > 2015山东信息学夏令营 Day5T3 路径
2015山东信息学夏令营 Day5T3 路径
问题描述：
给定平面上的n个点，定义(x1,y1)到(x2,y2)的费用为min(|x1-x2|,|y1-y2|)，求从1号点走到n号点的最小费用。
输入：
第一行包含一个正整数n，表示点数。
接下来n行，每行包含两个整数x[i],y[i](0<=x[i],y[i]<=10^9)，依次表示每个点的坐标。
输出：
一个整数，即最小费用。
输入输出样例：
path.in | path.out |
5 | 2
|
数据范围：
对于30%的数据，1<=n<=100；
对于60%的数据，1<=n<=1000；
对于全部的数据，1<=n<=200000；
思路：
1、60分直接最短路
2、对于坐标系中连续的三个点，(x1,y1),(x2,y2),(x3,y3)，总有min(x2-x1,y2-y1) + min(x3-x2,y3-y2) ≤ min(x3 - x1,y3 - y1)，所以在建图的时候，可以按x,y分别排一遍序，然后，相邻的点建边，这样边数为2*n，再用堆dij就可以了
代码：
#include<iostream>#include<cstdio>#include<string>#include<cstring>#include<algorithm>#include<vector>#include<queue>#define maxn 200005#define inf ~0U>>1using namespace std;struct point{ int x; int y; int pos;};struct orz{ int p; int d; friend bool operator < (orz a,orz b){ return a.d > b.d; }};struct edge{ int v; int w;};priority_queue< orz > ss;vector<edge> g[maxn];point pt[maxn];int flag = 0,v[maxn],d[maxn],n;bool cmpa(point a,point b){ return a.x < b.x;}bool cmpb(point a,point b){ return a.y < b.y;}void init(){ cin>>n; int tx,ty; for(int i = 1;i <= n;i++){ scanf("%d%d",&tx,&ty); pt[i].x = tx; pt[i].y = ty; pt[i].pos = i; } for(int i = 1;i <= n;i++) d[i] = inf; sort(pt+1,pt+1+n,cmpa); edge tmp; for(int i = 1;i < n;i++){ tmp.w = pt[i+1].x - pt[i].x; tmp.v = pt[i + 1].pos; g[pt[i].pos].push_back(tmp); tmp.v = pt[i].pos; g[pt[i+1].pos].push_back(tmp); } sort(pt+1,pt+1+n,cmpb); for(int i = 1;i < n;i++){ tmp.w = pt[i+1].y - pt[i].y; tmp.v = pt[i + 1].pos; g[pt[i].pos].push_back(tmp); tmp.v = pt[i].pos; g[pt[i+1].pos].push_back(tmp); }}void dij(){ orz tmp; d[1] = 0; tmp.p = 1; tmp.d = 0; ss.push(tmp); flag++; int to,wei,x,dd; edge j; while(!ss.empty()){ tmp = ss.top(); ss.pop(); x = tmp.p; dd = tmp.d; if(v[x] == flag) continue; v[x] = flag; for(int i = 0;i < g[x].size();i++){ j = g[x][i]; to = j.v; wei = j.w; if(d[to] > dd + wei){ d[to] = dd + wei; tmp.d = dd + wei; tmp.p = to; ss.push(tmp); } } } cout<<d[n];}int main(){ init(); dij(); return 0;}
2015山东信息学夏令营 Day5T3 路径
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。