1 #include<cstdio> 2 #include<cstring> 3 #include<queue> 4 #include<algorithm> 5 using namespace std; 6 #define N 51 7 #define K 51 8 #define M 2001 9 struct Point{int u,d;Point(const int &a,const int &b){d=a;u=b;}Point(){}};10 bool operator < (const Point &a,const Point &b){return a.d>b.d;}11 priority_queue<Point>q;12 int n,m,k,dis[N*K],ans=2147483647;13 bool vis[N*K];14 int first[M*K*2],next[M*K*2],v[M*K*2],w[M*K*2],en,x,y,z;15 void AddEdge(const int &U,const int &V,const int &W)16 {17     v[++en]=V;18     w[en]=W;19     next[en]=first[U];20     first[U]=en;21 }22 void dijkstra(const int &s)23 {24     memset(dis,0x7f,sizeof(dis));25     dis[s]=0; q.push(Point(0,s));26     while(!q.empty())27       {28         Point x=q.top(); q.pop();29         if(!vis[x.u])30           {31             vis[x.u]=0;32             for(int i=first[x.u];i;i=next[i])33               if(dis[v[i]]>dis[x.u]+w[i])34                 {35                   dis[v[i]]=dis[x.u]+w[i];36                   q.push(Point(dis[v[i]],v[i]));37                 }38           }39       }40     for(int i=0;i<=k;i++) ans=min(ans,dis[n+i*n]);41     printf("%d\n",ans);42 }43 int main()44 {45     scanf("%d%d%d",&n,&m,&k);46     for(int i=1;i<=m;i++)47       {48         scanf("%d%d%d",&x,&y,&z);49         AddEdge(x,y,z); AddEdge(y,x,z);50         for(int j=1;j<=k;j++)51           {52             AddEdge(x+j*n,y+j*n,z);53             AddEdge(y+j*n,x+j*n,z);54             AddEdge(x+(j-1)*n,y+j*n,z>>1);55             AddEdge(y+(j-1)*n,x+j*n,z>>1);56           }57       }58     dijkstra(1);59     return 0;60 }