思路：

这道题 不能把所有边都建出来 会MLE的！！！

oh gosh

其实不建所有的边 用的时候再调就行了….（也没啥区别）

//By SiriusRen

#include <queue>

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

#define N 100050

int n,m,k,first[N],v[N],w[N],next[N],tot,dis[N][21],vis[N][21],xx,yy,zz;

void add(int x,int y,int z){

    w[tot]=z,v[tot]=y,next[tot]=first[x],first[x]=tot++;

}

struct Node{int now,level,weight;}jy;

bool operator < (Node a,Node b){return a.weight>b.weight;}

void Dijkstra(){

    memset(dis,0x3f,sizeof(dis)),dis[1][0]=0;

    priority_queue<Node>pq;

    jy.now=1,pq.push(jy);

    while(!pq.empty()){

        Node t=pq.top();pq.pop();

        if(vis[t.now][t.level])continue;

        vis[t.now][t.level]=1;

        for(int i=first[t.now];~i;i=next[i]){

            if(!vis[v[i]][t.level]&&dis[v[i]][t.level]>dis[t.now][t.level]+w[i]){

                dis[v[i]][t.level]=dis[t.now][t.level]+w[i];

                jy.level=t.level,jy.now=v[i],jy.weight=dis[v[i]][t.level],pq.push(jy);

            }

            if(t.level<k&&!vis[v[i]][t.level+1]&&dis[v[i]][t.level+1]>dis[t.now][t.level]){

                dis[v[i]][t.level+1]=dis[t.now][t.level];

                jy.level=t.level+1,jy.now=v[i],jy.weight=dis[t.now][t.level],pq.push(jy);

            }

        }

    }

}

int main(){

    memset(first,-1,sizeof(first));

    scanf("%d%d%d",&n,&m,&k);

    for(int i=1;i<=m;i++){

        scanf("%d%d%d",&xx,&yy,&zz);

        add(xx,yy,zz),add(yy,xx,zz);

    }

    Dijkstra();

    printf("%d\n",dis[n][k]);

}