Bzoj 2834: 回家的路 dijkstra,堆优化,分层图,最短路

2834: 回家的路

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 62  Solved: 38
[Submit][Status][Discuss]

Description

Input

Output

Sample Input

2 1
1 2
1 1 2 2

Sample Output

5

HINT

N<=20000,M<=100000

Source

dijkstra+堆优化+分层图
把所有的横向和纵向分开看。跑最短路即可。
注意：N这么大，不能写N^2建图。要把M个位置去建图。

 #include<bits/stdc++.h>

 using namespace std;

 #define MAXN 20010

 #define MAXM 100010

 #define INF 1e9

 struct NODE

 {

     int begin,end,value,next;

 }edge[*MAXM+];

 struct node

 {

     int x,y,id;

 }a[MAXM+];

 int cnt,Head[*MAXM+],pos[*MAXM+],Heap[*MAXM+],dis[*MAXM+],N,SIZE;

 void addedge(int bb,int ee,int vv)

 {

     edge[++cnt].begin=bb;edge[cnt].end=ee;edge[cnt].value=vv;edge[cnt].next=Head[bb];Head[bb]=cnt;

 }

 void addedge1(int bb,int ee,int vv)

 {

     addedge(bb,ee,vv);addedge(ee,bb,vv);

 }

 int read()

 {

     int s=,fh=;char ch=getchar();

     while(ch<''||ch>''){if(ch=='-')fh=-;ch=getchar();}

     while(ch>=''&&ch<=''){s=s*+(ch-'');ch=getchar();}

     return s*fh;

 }

 //int xy(int x,int y){return (x-1)*n+y;}

 void Push1(int k)

 {

     int now=k,root;

     while(now>)

     {

         root=now/;

         if(dis[Heap[root]]<=dis[Heap[now]])return;

         swap(Heap[root],Heap[now]);

         swap(pos[Heap[root]],pos[Heap[now]]);

         now=root;

     }

 }

 void Insert(int k)

 {

     Heap[++SIZE]=k;pos[k]=SIZE;Push1(SIZE);

 }

 void Pop1(int k)

 {

     int now,root=k;

     pos[Heap[k]]=;Heap[k]=Heap[SIZE--];if(SIZE>)pos[Heap[k]]=k;

     while(root<=SIZE/)

     {

         now=root*;

         if(now<SIZE&&dis[Heap[now+]]<dis[Heap[now]])now++;

         if(dis[Heap[root]]<=dis[Heap[now]])return;

         swap(Heap[root],Heap[now]);

         swap(pos[Heap[root]],pos[Heap[now]]);

         root=now;

     }

 }

 void dijkstra(int start)

 {

     int i,u,v;

     for(i=;i<=N;i++)dis[i]=INF;dis[start]=;

     for(i=;i<=N;i++)Insert(i);

     while(SIZE>)

     {

         u=Heap[];Pop1(pos[u]);

         for(i=Head[u];i!=-;i=edge[i].next)

         {

             v=edge[i].end;

             if(dis[v]>dis[u]+edge[i].value){dis[v]=dis[u]+edge[i].value;Push1(pos[v]);}

         }

     }

 }

 bool cmp1(node aa,node bb)

 {

     if(aa.x==bb.x)return aa.y<bb.y;

     return aa.x<bb.x;

 }

 bool cmp2(node aa,node bb)

 {

     if(aa.y==bb.y)return aa.x<bb.x;

     return aa.y<bb.y;

 }

 int main()

 {

     int n,m,i,k,k1,bx,by,ex,ey;

     n=read();m=read();

     memset(Head,-,sizeof(Head));cnt=;

     N=*m+;

     for(i=;i<=m+;i++)a[i].x=read(),a[i].y=read(),a[i].id=i;

     sort(a+,a+m+,cmp1);

     for(i=;i<=m+;i++)

     {

         if(a[i].x==a[i+].x)addedge1(a[i].id,a[i+].id,*(a[i+].y-a[i].y));

     }

     sort(a+,a+m+,cmp2);

     for(i=;i<=m+;i++)

     {

         if(a[i].y==a[i+].y)addedge1(a[i].id+m+,a[i+].id+m+,*(a[i+].x-a[i].x));

     }

     for(i=;i<=m;i++)addedge1(i,i+m+,);

     addedge1(m+,m++m+,);addedge1(m+,m++m+,);

     dijkstra(m+);

     if(dis[m+]!=INF)printf("%d",dis[m+]);

     else printf("-1");

     /*不看n的范围的后果。。。写了个n^2的建图。。。

     for(i=1;i<=m;i++)

     {

         x=read();y=read();

         k=xy(x,y);

         addedge1(k,n*n+k,1);

     }

     for(i=1;i<=n;i++)

     {

         for(j=1;j<=n;j++)

         {

             if(i<n){k=xy(i,j);k1=xy(i+1,j);addedge1(k,k1,2);addedge1(k+n*n,k1+n*n,2);}

             if(j<n){k=xy(i,j);k1=xy(i,j+1);addedge1(k,k1,2);addedge1(k+n*n,k1+n*n,2);}

         }

     }

     N=2*n*n;

     bx=read();by=read();ex=read();ey=read();

     addedge1(xy(bx,by),xy(bx,by)+n*n,0);

     addedge1(xy(ex,ey),xy(ex,ey)+n*n,0);

     dijkstra(xy(bx,by));

     if(dis[xy(ex,ey)]!=INF)printf("%d",dis[xy(ex,ey)]);

     else printf("-1");*/

     fclose(stdin);

     fclose(stdout);

     return ;

 }

Bzoj 2834: 回家的路 dijkstra,堆优化,分层图,最短路的相关教程结束。