即求从起点到终点至少走K条路的最短路径。
用两个变量来维护一个点的dis，u和e，u为当前点的编号，e为已经走过多少条边，w[u][e]表示到当前点，走过e条边的最短路径长度，因为是至少K条边，所以大于K条边的当做K条边来处理就好了。求最短路的三个算法都可以做，我这里用的是SPFA，比较简洁。
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#define Mod 1000000007
using namespace std;
#define N 5007 vector<pair<int,int> > G[N];
int w[N][],inq[N][];
int s,t,n,m,k,res;
struct node
{
int u,e;
node(int _u,int _e)
{
u = _u;
e = _e;
}
node(){}
}; void SPFA(int s)
{
int u,v,e,i,j,len;
for(i=;i<=n;i++)
{
for(j=;j<=;j++)
{
w[i][j] = Mod;
inq[i][j] = ;
}
}
queue<node> que;
res = Mod;
while(!que.empty())
que.pop();
w[s][] = ;
inq[s][] = ;
que.push(node(s,));
while(!que.empty())
{
node tmp = que.front();
que.pop();
u = tmp.u;
e = tmp.e;
if(u == t && e == k)
res = min(w[u][e],res);
inq[u][e] = ; //释放
int ka;
if(e+ > k)
ka = k;
else
ka = e+;
for(i=;i<G[u].size();i++)
{
v = G[u][i].first;
len = G[u][i].second;
if(w[v][ka] > len + w[u][e])
{
w[v][ka] = len + w[u][e];
if(!inq[v][ka])
{
inq[v][ka] = ;
que.push(node(v,ka));
}
}
}
}
} int main()
{
int u,v,wi,i,j;
while(scanf("%d%d",&n,&m)!=EOF)
{
for(i=;i<=;i++)
G[i].clear();
while(m--)
{
scanf("%d%d%d",&u,&v,&wi);
G[u].push_back(make_pair(v,wi));
G[v].push_back(make_pair(u,wi));
}
scanf("%d%d%d",&s,&t,&k);
SPFA(s);
if(res == Mod)
puts("-1");
else
printf("%d\n",res);
}
return ;
}