刚来洛谷随机的题，bfs不知道为什么只过俩点，可能是我太菜了QaQ，但是用dfs一遍就过了……

翻一翻题解区好像没有比这更简单的代码了

#include <bits/stdc++.h>
using namespace std;
#define N 55
int t[N][N];
int n,m,k;
int minn=1000000000;
bool flag[N];
void dfs(int x,int time,int k1){
	if(x==n&&time<minn){
		minn=time;
		return;
	}
	if(time>=minn)return;
	flag[x]=1;
	for(int i=1;i<=n;i++){
		if(t[x][i]!=0&&flag[i]!=1){
			dfs(i,time+t[x][i],k1);
			if(k1>0)dfs(i,time+(t[x][i]/2),k1-1);
		}
	}
	flag[x]=0;
	return;
}
int main(){
	cin>>n>>m>>k;
	for(int i=1;i<=m;i++){
		int a,b,time;
		cin>>a>>b>>time;
		t[a][b]=time;
		t[b][a]=time;
	}
	memset(flag,0,N);
	dfs(1,0,k);
	cout<<minn;
	return 0;
}