直接写一个队列会WA!!!(WA了好几次)
所以改用优先队列,一遍过掉。
这个题思路挺简单的: 虽然说是要|x1-x2|和|y1-y2|的最小值,但是没什么意义,不如直接建两条边权值分别为|x1-x2|和|y1-y2|,然后跑一遍Dij!由于你要到达的是点n,那么建边只需要从左往右排序后顺次建边,再从下到上排序顺次建边,跑最短路就好了!
(注意,为了防止一个点多次进入队列造成时间浪费,应该用一个标记避免这种情况发生,这里我用了exp)
&&我可能会防止你们复制代码。
#include<queue> #include<vector> #include<cstdio> #include<string> #include<cstring> #include<iostream> #include<algorithm> #define why pair<long long,int> using namespace std; const int M=2e5+10; int n,vis[M]; long long dis[M]; bool exp[M]; struct node{ int x,y,id; }p[M]; int cnt,head[M<<2]; struct edge{ int to,nxt; long long w; }e[M<<2]; priority_queue< why,vector<why>,greater<why> > Q; inline void Add(int x,int y,int z){ cnt++; e[cnt].to=y; e[cnt].nxt=head[x]; e[cnt].w=z; head[x]=cnt; } inline bool CMP1(node a,node b){ return a.x<b.x; } inline bool CMP2(node a,node b){ return a.y<b.y; } void Dij(){ memset(vis,0,sizeof(vis)); memset(dis,0x3f3f3f3f,sizeof(dis)); Q.push(make_pair(0,1)); dis[1]=0; while(!Q.empty()){ int u=Q.top().second; Q.pop(); if(exp[u]) continue; exp[u]=true; for(int i=head[u];i;i=e[i].nxt){ int v=e[i].to; if(dis[v]>dis[u]+e[i].w){ dis[v]=dis[u]+e[i].w; Q.push(make_pair(dis[v],v)); } } } } int main(){ scanf("%d",&n); for(int i=1;i<=n;i++){ int x,y; scanf("%d%d",&x,&y); p[i].x=x,p[i].y=y,p[i].id=i; } sort(p+1,p+n+1,CMP1); for(int i=1;i<n;i++) Add(p[i].id,p[i+1].id,p[i+1].x-p[i].x),Add(p[i+1].id,p[i].id,p[i+1].x-p[i].x); sort(p+1,p+n+1,CMP2); for(int i=1;i<n;i++) Add(p[i].id,p[i+1].id,p[i+1].y-p[i].y),Add(p[i+1].id,p[i].id,p[i+1].y-p[i].y); Dij(); printf("%lld\n",dis[n]); return 0; }