1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<string> 5 #include<cstdlib> 6 #include<ctime> 7 #include<vector> 8 #include<algorithm> 9 #include<queue>10 using namespace std;11 #define LL long long12 const int maxn=10010;13 const int inf=1000000000;14 struct node{15     int x,y,next;16     int v;17 }e[maxn*10];18 int linkk[maxn],len=0;19 int n,m,k;20 LL d[maxn][25];21 void insert(int x,int y,int v){22     e[++len].y=y;23     e[len].x=x;24     e[len].next=linkk[x];25     linkk[x]=len;26     e[len].v=v;27 }28 void init(){29     scanf("%d%d%d",&n,&m,&k);30     int x,y,v;31     for(int i=1;i<=m;i++){32         scanf("%d%d%d",&x,&y,&v);33         insert(x,y,v);insert(y,x,v);34     }35 }36 struct bian{37     int x,k;38     LL w;39     bian(int a,int b,LL c){x=a,k=b,w=c;}40     bool operator>(const bian& b)const{41         return w>b.w;42     } 43 };44 priority_queue<bian,vector<bian>,greater<bian> > q;45 void dij(){46     memset(d,10,sizeof(d));47     for(int i=0;i<=k;i++)d[1][i]=0;48     q.push(bian(1,0,0));49     while(!q.empty()){50         bian tmp=q.top();51         q.pop();52         int x=tmp.x;53         int p=tmp.k;54         LL w=tmp.w;55         for(int i=linkk[x];i;i=e[i].next){56             if(p<k&&w<d[e[i].y][p+1]){57                 d[e[i].y][p+1]=w;58                 q.push(bian(e[i].y,p+1,w));59             }60             if(w+e[i].v<d[e[i].y][p]){61                 d[e[i].y][p]=w+e[i].v;62                 q.push(bian(e[i].y,p,d[e[i].y][p]));63             }64         }65     }66 }67 void work(){68     dij();69     cout<<d[n][k]<<endl;70 }71 int main(){72     init();73     work();74 }