codeforces（D. Returning Home）（建图+dijkstra）

原题链接

//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")
//#pragma GCC optimization ("unroll-loops")
#include 
#define pb push_back
#define ll long long
#define IOS std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
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;
}
using namespace std;ll n,m,sx,sy,fx,fy,len,inf=0x3f3f3f3f3f3f3f;
ll x[100005],y[100005];
struct node
{ll to,next,w;
}e[1000006];
ll head[1000006],cnt;
ll dis[400005];
bool vis[400005];
struct NODE
{ll x,y,id;
}v[100005];
struct Node
{ll id,val;bool operator <(const Node &a)const{return a.val<val;}
};
priority_queue<Node> q;
bool cmp(NODE a,NODE b)//以x排序
{if(a.x<b.x){return 1;}return 0;
}
bool CMP(NODE a,NODE b)//以y排序
{if(a.y<b.y){return 1;}return 0;
}
void add(ll u,ll v,ll w)
{e[cnt].to=v;e[cnt].w=w;e[cnt].next=head[u];head[u]=cnt++;
}
void dijkstra()
{memset(dis,inf,sizeof(dis));dis[0]=0;q.push({0,0});while(!q.empty()){Node u=q.top();q.pop();if(vis[u.id]!=0){continue;}vis[u.id]=1;for(int i=head[u.id];i!=-1;i=e[i].next){ll vv=e[i].to;if(dis[vv]>dis[u.id]+e[i].w){dis[vv]=dis[u.id]+e[i].w;if(vis[vv]==0){q.push({vv,dis[vv]});}}}}
}
int main()
{memset(head,-1,sizeof(head));n=read();m=read();sx=read();sy=read();fx=read();fy=read();for(int i=1;i<=m;i++){v[i].x=read();v[i].y=read();v[i].id=i;}len=abs(fx-sx)+abs(fy-sy);add(0,111111,len);add(111111,0,len);for(int i=1;i<=m;i++){len=min(abs(v[i].x-sx),abs(v[i].y-sy));add(0,v[i].id,len);add(v[i].id,0,len);len=abs(fx-v[i].x)+abs(fy-v[i].y);add(v[i].id,111111,len);add(111111,v[i].id,len);}sort(v+1,v+1+m,cmp);for(int i=2;i<=m;i++){len=min(abs(v[i].x-v[i-1].x),abs(v[i].y-v[i-1].y));add(v[i-1].id,v[i].id,len);add(v[i].id,v[i-1].id,len);}sort(v+1,v+1+m,CMP);for(int i=2;i<=m;i++){len=min(abs(v[i].x-v[i-1].x),abs(v[i].y-v[i-1].y));add(v[i-1].id,v[i].id,len);add(v[i].id,v[i-1].id,len);}dijkstra();printf("%lld\n",dis[111111]);return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！