题目链接：

思路：dist[i][j]表示到顶点i走了k条路所花费的最小时间，为了节省内存，当j>=k时，直接令j=k即可，然后就是二维spfa求最短路了。

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #include
           
             7 using namespace std; 8 #define MAXN 5555 9 #define inf 1<<3010 struct Node{11 int v,w;12 };13 vector
            
             map[MAXN];14 typedef pair
             
              Pair;15 16 int dist[MAXN][55];//表示到i点经过j条路的最小花费17 bool mark[MAXN][55];18 int n,m,st,ed,k;19 20 void spfa(){21 for(int i=0;i<=n;i++)22 for(int j=0;j<55;j++)23 dist[i][j]=inf;24 memset(mark,false,sizeof(mark));25 mark[st][0]=true;26 dist[st][0]=0;27 queue
              
               Q;28 Q.push(make_pair(st,0));29 while(!Q.empty()){30 Pair pp=Q.front();31 Q.pop();32 int u=pp.first;33 int step=pp.second;34 mark[u][step]=false;35 for(int i=0;i
               
                k)nstep=k;40 if(dist[v][nstep]>dist[u][step]+w){41 dist[v][nstep]=dist[u][step]+w;42 if(!mark[v][nstep]){ mark[v][nstep]=true;Q.push(make_pair(v,nstep)); }43 }44 }45 }46 }47 48 int main(){49 int u,v,w;50 while(~scanf("%d%d",&n,&m)){51 for(int i=0;i<=n;i++)map[i].clear();52 for(int i=1;i<=m;i++){53 scanf("%d%d%d",&u,&v,&w);54 Node p1,p2;55 p1.v=v,p1.w=w;56 p2.v=u,p2.w=w;57 map[u].push_back(p1);58 map[v].push_back(p2);59 }60 scanf("%d%d%d",&st,&ed,&k);61 k=k/10+(k%10!=0);62 spfa();63 if(dist[ed][k]!=inf){64 printf("%d\n",dist[ed][k]);65 }else66 puts("-1");67 }68 return 0;69 }