最短路问题，用spfa解决
设dis[i][j]表示由原点走到i节点用了j个宝石的最短路长度 dis[i][j]=min(dis[u][j]+G[u][i],dis[u][j-1],dis[i][j]) 下面附上代码：
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<queue>
using namespace std;
const int inf=0x3f3f3f3f;
int n,p,k;
int pos=0;
int dis[10001][11];
int head[10001];
bool used[10001];
queue<int>Q;
struct edge{int to,next,c;}e[1000001*3];
void addedge(int a,int b,int c)
{pos++; e[pos].to=b,e[pos].next=head[a],e[pos].c=c;head[a]=pos;}
void spfa()
{for(int i=1;i<=n;i++)for(int j=0;j<=k;j++)dis[i][j]=inf;used[1]=1;for(int i=0;i<=k;i++)dis[1][i]=0;Q.push(1);while(!Q.empty()){int u=Q.front();Q.pop();used[u]=0;for(int i=head[u];i;i=e[i].next){int v=e[i].to,c=e[i].c;for(int j=0;j<=k;j++){if(dis[v][j]>dis[u][j-1]&&j){dis[v][j]=dis[u][j-1];if(!used[v]){used[v]=1;Q.push(v);}}if(dis[v][j]>dis[u][j]+c){dis[v][j]=dis[u][j]+c;if(!used[v]){used[v]=1;Q.push(v);}}}}}
}
int main()
{int a,b,c;scanf("%d%d%d",&n,&p,&k);for(int i=1;i<=p;i++){scanf("%d%d%d",&a,&b,&c);addedge(a,b,c);}spfa();cout<<dis[n][k]<<endl;
}