第一次写分层图(捂脸)

一开始真的naive地建图了，T到飞起..

可以省下建图的空间，直接在dis数组上拓展一维，同时维护点的编号和高度。

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;inline int rd(){    int ret=0,f=1;char c;    while(c=getchar(),!isdigit(c))f=c=='-'?-1:1;    while(isdigit(c))ret=ret*10+c-'0',c=getchar();    return ret*f;}const int MAXN=2048*4;struct Edge{    int next,to,w;}e[1000000];int ecnt,head[MAXN];inline void add(int x,int y,int w){    e[++ecnt].next = head[x];    e[ecnt].to = y;    e[ecnt].w = w;    head[x] = ecnt;}int n,m,num;queue
         
           Q,Qk;int dis[MAXN][64],inq[MAXN][64];void spfa(){    memset(dis,0x3f,sizeof(dis));    Q.push(1);Qk.push(0);dis[1][0]=0;inq[1][0]=1;    while(!Q.empty()){        int top=Q.front();Q.pop();int tmp=Qk.front();Qk.pop();        inq[top][tmp]=0;        for(int i=head[top];i;i=e[i].next){            int v=e[i].to;            if(dis[v][tmp]>dis[top][tmp]+e[i].w){                dis[v][tmp]=dis[top][tmp]+e[i].w;                if(!inq[v][tmp]) Q.push(v),Qk.push(tmp),inq[v][tmp]=1;            }            if(tmp
          
           dis[top][tmp]+(e[i].w>>1)){ dis[v][tmp+1]=dis[top][tmp]+(e[i].w>>1); if(!inq[v][tmp+1]) Q.push(v),Qk.push(tmp+1),inq[v][tmp+1]=1; } } }}int main(){ n=rd();m=rd();num=rd(); int x,y,w; for(int i=1;i<=m;i++){ x=rd();y=rd();w=rd(); add(x,y,w);add(y,x,w); } spfa(); int ans=1<<30; for(int i=0;i<=num;i++)ans=min(ans,dis[n][i]); cout<