1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #define pa pair
         
           6 #define inf 0x7fffffff 7 #define M 400008 8 using namespace std; 9 int d[M],f[M],n,m,k,s,t,cnt,head[M],next[10*M],u[10*M],v[10*M];10 void jia(int a1,int a2,int a3)11 {12     cnt++;13     next[cnt]=head[a1];14     head[a1]=cnt;15     u[cnt]=a2;16     v[cnt]=a3;17     return;18 }19 int main()20 {21     scanf("%d%d%d",&n,&m,&k);22     scanf("%d%d",&s,&t);23     for(int i=1;i<=m;i++)24       {25         int a1,a2,a3;26         scanf("%d%d%d",&a1,&a2,&a3);27         jia(a1,a2,a3);28         jia(a2,a1,a3);29         for(int j=1;j<=k;j++)30           {31             jia(j*n+a1,j*n+a2,a3);32             jia(j*n+a2,j*n+a1,a3);33             jia((j-1)*n+a1,j*n+a2,0);34             jia((j-1)*n+a2,j*n+a1,0);35           }36       }37     priority_queue
          
           
            ,greater
            
              >q;38 memset(d,60,sizeof(d));39 q.push(make_pair(0,s));40 d[s]=0;41 for(;!q.empty();)42 {43 int now=q.top().second;44 q.pop();45 if(f[now])46 continue;47 f[now]=1;48 for(int i=head[now];i;i=next[i])49 if(d[u[i]]>d[now]+v[i])50 {51 d[u[i]]=d[now]+v[i];52 q.push(make_pair(d[u[i]],u[i]));53 }54 }55 int ans=inf;56 for(int i=0;i<=k;i++)57 ans=min(ans,d[i*n+t]);58 printf("%d\n",ans);59 return 0;60 }
            
           
          
         
        
       
      
     

分层图按k分层