给出平面上n个点坐标,点(x1,y1)和点(x2,y2)之间有权值为\(min(abs(x1-x2),abs(y1-y2))\)的边,求1到n的最短路.
老早就知道有这么个题但是一直不会 也许这就是蒟蒻吧.jpg 首先我们可以在(x1,y1)和(x2,y2)之间连两条边,权值分别为abs(x1-x2),abs(y1-y2),然后跑最短路,答案显然不变. 然后我们发现,对从左向右三个点A(x1,y1),B(x2,y2),C(x3,y3),满足x1<=x2<=x3,我们在AB之间连了权值为abs(x1-x2)的边,BC之间连了权值为abs(x2-x3)的边,就不需要在AC之间连权值为abs(x1-x3)的边了. 于是只需按横坐标排序后相邻的点之间连n-1条双向边,按纵坐标排序后相邻的点之间连n-1条双向边.这个边数就可以跑dijkstra了. 这个题还有个最小生成树版本:AtCoder Regular Contest 076D Built?
#include<cstdio> #include<queue> #include<algorithm> using namespace std; const int maxn=200005,maxm=1000005; struct edge{ int to,next,w; }lst[maxm];int len=1,first[maxn]; void addedge(int a,int b,int w){ lst[len].to=b;lst[len].w=w;lst[len].next=first[a];first[a]=len++; } struct node{ int v,d; node(){} node(int _v,int _d){v=_v;d=_d;} bool operator <(const node &B)const{ return d>B.d; } }; bool vis[maxn];int dis[maxn]; int n; void dijkstra(){ for(int i=1;i<=n;++i)dis[i]=0x7f7f7f7f; dis[1]=0; priority_queue<node> q; q.push(node(1,0)); while(!q.empty()){ node tmp=q.top();q.pop(); if(vis[tmp.v])continue; vis[tmp.v]=true; for(int pt=first[tmp.v];pt;pt=lst[pt].next){ if(!vis[lst[pt].to]&&dis[lst[pt].to]>tmp.d+lst[pt].w){ dis[lst[pt].to]=tmp.d+lst[pt].w; q.push(node(lst[pt].to,tmp.d+lst[pt].w)); } } } } int x[maxn],y[maxn]; int seq[maxn]; bool cmpx(const int &a,const int &b){ return x[a]<x[b]; } bool cmpy(const int &a,const int &b){ return y[a]<y[b]; } int main(){ scanf("%d",&n); for(int i=1;i<=n;++i)scanf("%d%d",x+i,y+i); for(int i=1;i<=n;++i)seq[i]=i; sort(seq+1,seq+n+1,cmpx); for(int i=1;i<n;++i){ addedge(seq[i],seq[i+1],x[seq[i+1]]-x[seq[i]]); addedge(seq[i+1],seq[i],x[seq[i+1]]-x[seq[i]]); } sort(seq+1,seq+n+1,cmpy); for(int i=1;i<n;++i){ addedge(seq[i],seq[i+1],y[seq[i+1]]-y[seq[i]]); addedge(seq[i+1],seq[i],y[seq[i+1]]-y[seq[i]]); } dijkstra(); printf("%d\n",dis[n]); return 0; }转载于:https://www.cnblogs.com/liu-runda/p/7103297.html
相关资源：数据结构—成绩单生成器