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