BZOJ 2763 分层图最短路

突然发现我不会分层图最短路，写一发。　就是同层中用双向边相连，用单向边连下一层

 #include <cstdio>

 #include <algorithm>

 #include <iostream>

 #include <string>

 #include <cstring>

 #include <queue>

 #include <vector>

 #define pa pair<int,int>

 #define mp make_pair

 #define fi first

 #define se second

 using namespace std;

 const int Maxm=;

 const int Maxn=;

 const int Inf=0x3f3f3f3f;

 priority_queue<pa,vector<pa>,greater<pa> > Q;

 int head[Maxn],dis[Maxn],n,m,k,S,T,u,v,w,cnt;

 struct Edge{int to,next,w;}edge[Maxm];

 inline void Add(int u,int v,int w)

 {edge[cnt].to=v;edge[cnt].next=head[u];edge[cnt].w=w;head[u]=cnt++;}

 inline void ADD(int u,int v,int w) {Add(u,v,w),Add(v,u,w);}

 inline int Get(int u,int Dep) {return u+(Dep-)*n;}

 void Dij()

 {

     Q.push(mp(,Get(S,)));

     for (int i=;i<=Get(n,k);i++) dis[i]=Inf;

     dis[Get(S,)]=;

     while (!Q.empty())

     {

         int u=Q.top().se; Q.pop();

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

             if (dis[u]+edge[i].w<dis[edge[i].to])

             {

                 dis[edge[i].to]=dis[u]+edge[i].w;

                 Q.push(mp(dis[edge[i].to],edge[i].to));

             }

     }

 }

 int main()

 {

     scanf("%d%d%d",&n,&m,&k); k++;

     scanf("%d%d",&S,&T); S++,T++;

     memset(head,-,sizeof(head));

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

     {

         scanf("%d%d%d",&u,&v,&w); u++,v++;

         for (int j=;j<=k;j++) ADD(Get(u,j),Get(v,j),w);

         for (int j=;j<k;j++)

             Add(Get(u,j),Get(v,j+),),

             Add(Get(v,j),Get(u,j+),);

     }

     Dij();

     printf("%d\n",dis[Get(T,k)]);

     return ;

 }

C++