BZOJ 4152: [AMPPZ2014]The Captain(最短路)
2018-06-17 21:10:16来源:未知 阅读 ()
Submit: 1550 Solved: 619
[Submit][Status][Discuss]
Description
Input
Output
Sample Input
2 2
1 1
4 5
7 1
6 7
Sample Output
HINT
Source
鸣谢Claris上传
很有意思的一道题目
两个点之间的费用为min(|x1-x2|,|y1-y2|),就相当于对于x和y分别连边。
对于1,2,3这三个点,若x1<=x2<=x3,不难发现|x1-x3|这条边没有必要连。
那么我们把所有点按x排序,每个点向相邻点连权值为x差的绝对值的边。
再把所有点按y排序,同理。
然后直接跑最短路即可。
记得开long long
#include<cstdio> #include<algorithm> #include<queue> #include<cstring> #define Pair pair<int,int> #define F first #define S second #define int long long const int MAXN=1e6+10; using namespace std; inline int read() { char c=getchar();int x=0,f=1; while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f; } int N; struct node { int id,x,y; }Point[MAXN]; int comp(const node &a,const node &b){return a.x<b.x;} int comp2(const node &a,const node &b){return a.y<b.y;} int dis[MAXN],vis[MAXN]; struct E { int u,v,w,nxt; }edge[MAXN]; int head[MAXN],num=1; inline void AddEdge(int x,int y,int z) { edge[num].u=x;edge[num].v=y;edge[num].w=z;edge[num].nxt=head[x]; head[x]=num++; } void Dijstra() { memset(dis,0xf,sizeof(dis));dis[1]=0; priority_queue<Pair>q; q.push(make_pair(0,1)); while(q.size()!=0) { while(vis[q.top().S]&&q.size()>0) q.pop(); Pair p=q.top(); vis[p.S]=1; for(int i=head[p.S];i!=-1;i=edge[i].nxt) if(dis[edge[i].v]>dis[p.S]+edge[i].w) dis[edge[i].v]=dis[p.S]+edge[i].w, q.push(make_pair(-dis[edge[i].v],edge[i].v)); } printf("%lld",dis[N]); } main() { #ifdef WIN32 freopen("a.in","r",stdin); #else #endif memset(head,-1,sizeof(head)); N=read(); for(int i=1;i<=N;i++) Point[i].id=i,Point[i].x=read(),Point[i].y=read(); sort(Point+1,Point+N+1,comp); for(int i=1;i<=N-1;i++) AddEdge(Point[i].id,Point[i+1].id,Point[i+1].x-Point[i].x), AddEdge(Point[i+1].id,Point[i].id,Point[i+1].x-Point[i].x); sort(Point+1,Point+N+1,comp2); for(int i=1;i<=N-1;i++) AddEdge(Point[i].id,Point[i+1].id,Point[i+1].y-Point[i].y), AddEdge(Point[i+1].id,Point[i].id,Point[i+1].y-Point[i].y); Dijstra(); return 0; }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- bzoj3569 DZY Loves Chinese II 2020-05-25
- bzoj4036 [HAOI2015]按位或 2020-04-26
- 「BZOJ4173」数学 2020-01-15
- bzoj3944 Sum 2019-12-25
- BZOJ1008: [HNOI2008]越狱(快速幂) 2019-08-26
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash