解题：SHOI 2012 回家的路

题面

完了，做的时候已经想不起来分层图这个东西了QAQ

对于这种“多种”路径加中转站的题，还有那种有若干次“特殊能力”的题，都可以考虑用分层图来做

显然只需要记录所有的中转站+起点终点，然后拆出横竖两层，一层的点之间连值为$2$的边，每个站的两层之间连值为$1$的边，然后再跑最短路。注意数组大小，还有起点和终点的两层是连零边的

 #include<queue>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 const int N=,inf=0x3f3f3f3f;

 struct a

 {

     int xx,yy,id;

 }mem[N];

 struct b{int node,dist;};

 bool operator < (b x,b y)

 {

     return x.dist>y.dist;

 }

 priority_queue<b> hp;

 int val[*N],dis[*N],vis[*N];

 int p[*N],noww[*N],goal[*N];

 int n,m,t1,t2,st,ed,cnt,tot;

 bool cmp1(a x,a y)

 {

     return x.xx==y.xx?x.yy<y.yy:x.xx<y.xx;

 }

 bool cmp2(a x,a y)

 {

     return x.yy==y.yy?x.xx<y.xx:x.yy<y.yy;

 }

 void link(int f,int t,int v)

 {

     noww[++cnt]=p[f],p[f]=cnt;

     goal[cnt]=t,val[cnt]=v;

 }

 void Dijkstra(int s)

 {

     memset(dis,0x3f,sizeof dis);

     dis[s]=,hp.push((b){s,});

     while(!hp.empty())

     {

         b tt=hp.top(); hp.pop(); int tn=tt.node;

         if(vis[tn]) continue ; vis[tn]=true;

         for(int i=p[tn];i;i=noww[i])

             if(dis[goal[i]]>dis[tn]+val[i])

                 dis[goal[i]]=dis[tn]+val[i],hp.push((b){goal[i],dis[goal[i]]});

     }

 }

 int main ()

 {

     scanf("%d%d",&n,&m),st=++m,ed=++m;

     link(st,st+m,),link(st+m,st,);

     link(ed,ed+m,),link(ed+m,ed,);

     for(int i=;i<=ed;i++)

     {

         scanf("%d%d",&mem[i].xx,&mem[i].yy);

         mem[i].id=++tot,link(tot,tot+m,),link(tot+m,tot,);

     }

     sort(mem+,mem++tot,cmp1);

     for(int i=;i<=st;i++)

         if(mem[i].xx==mem[i+].xx)

         {

             link(mem[i].id,mem[i+].id,*(mem[i+].yy-mem[i].yy));

             link(mem[i+].id,mem[i].id,*(mem[i+].yy-mem[i].yy));

         }

     sort(mem+,mem++tot,cmp2);

     for(int i=;i<=st;i++)

         if(mem[i].yy==mem[i+].yy)

         {

             link(mem[i].id+m,mem[i+].id+m,*(mem[i+].xx-mem[i].xx));

             link(mem[i+].id+m,mem[i].id+m,*(mem[i+].xx-mem[i].xx));

         }

     Dijkstra(st),dis[ed]>=inf?printf("-1"):printf("%d",dis[ed]);

     return ;

 }