记录编号	134407	评测结果	AAAAAAAAAA
题目名称	旅行	最终得分	100
用户昵称	水中音	是否通过	通过
代码语言	C++	运行时间	0.025 s
提交时间	2014-10-30 06:35:46	内存使用	0.48 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int qwq=0x7fffffff;
bool flag[11][110]={0},flag1[101]={0},flag2[101]={0},flag3;
int n,m,k,i,j,l,zj1,zj2,zj3,p,ans;
int to[101][101]={0},street[101][101]={0},reto[101][101]={0},setbh[101]={0},A[1001]={0},zui[11][1001]={0},B[1001]={0};
void init()
{
	n--;
	for(i=1;i<=m;i++)
	{
		scanf("%d%d%d",&zj1,&zj2,&zj3);
		if(street[zj1][zj2]==0)
		{
			to[zj1][0]++;
			to[zj1][ to[zj1][0] ]=zj2;
			street[zj1][zj2]=zj3;

			reto[zj2][0]++;
			reto[zj2][ reto[zj2][0] ]=zj1;
		}
		else
		if(zj3<street[zj1][zj2]) street[zj1][zj2]=zj3;
	}
}
void firstdfs(int x)
{
    flag1[x]=true;
	for(int h=1;h<=to[x][0];h++)
	if(!flag1[ to[x][h] ])
	firstdfs(to[x][h]);
	A[0]++;
	A[ A[0] ]=x;
}
void seconddfs(int x)
{
    flag2[x]=true;
	setbh[x]=p;
	for(int h=1;h<=reto[x][0];h++)
	if(flag1[ reto[x][h] ]&&!flag2[ reto[x][h] ])
	seconddfs(reto[x][h]);
}
void doublespfa()
{
	for(i=0;i<=k;i++)
	for(p=0;p<=n;p++)
	zui[i][p]=qwq;
	zui[0][0]=0;
	A[0]=1;A[1]=0;B[1]=0;
	flag[0][0]=true;
	while(A[0])
	{
		zj1=A[ A[0] ];zj2=B[ A[0] ];
		A[0]--;
		flag[zj2][zj1]=false;
		for(i=1;i<=to[zj1][0];i++)
		{
			if(setbh[ to[zj1][i] ]==setbh[zj1])
			{
				zj3=zui[zj2][zj1]+street[zj1][ to[zj1][i] ];
				if(zui[zj2][ to[zj1][i] ]>zj3)
				{
					zui[zj2][ to[zj1][i] ]=zj3;
					if(!flag[zj2][ to[zj1][i] ])
					{
						A[0]++;
						A[ A[0] ]=to[zj1][i];
						B[ A[0] ]=zj2;
						flag[zj2][ to[zj1][i] ]=true;
					}
				}
			}
			else
			{
                if(zj2>=k)continue;
                zj3=street[zj1][ to[zj1][i] ]<<1;
				zj3+=zui[zj2][zj1];
				if(zui[zj2+1][ to[zj1][i] ]>zj3)
				{
					zui[zj2+1][ to[zj1][i] ]=zj3;
					if(!flag[zj2+1][to[zj1][i]])
					{
						A[0]++;
						A[ A[0] ]=to[zj1][i];
						B[ A[0] ]=zj2+1;
						flag[zj2+1][ to[zj1][i] ]=true;
					}
				}
			}
		}
	}
}
void getnum()
{
	p=0;
	for(i=0;i<=n;i++)
	if(!flag1[i])
	{
		A[0]=0;
		firstdfs(i);
		for(j=A[0];j>0;j--)
		if(!flag2[ A[j] ])
		p++,seconddfs(A[j]);
	}
}
int vocaloid()
{
	init();
	getnum();
	doublespfa();
	flag3=false;
	ans=qwq;
	for(i=0;i<=k;i++)
	if(zui[i][n]!=qwq)
	{
		flag3=true;
		if(ans>zui[i][n])ans=zui[i][n];
	}
	if(flag3)printf("%d\n",ans);
	else printf("-1\n");
}
void shit()
{
	memset(flag1,0,sizeof(flag1));//1
	memset(flag2,0,sizeof(flag2));//2
	memset(to,0,sizeof(to));//3
	memset(reto,0,sizeof(reto));//4
	memset(street,0,sizeof(street));//5
	memset(setbh,0,sizeof(setbh));//6!
	memset(A,0,sizeof(A));//7!!
	memset(B,0,sizeof(B));//8!!!
	memset(zui,0,sizeof(zui));//9!!!
}
int main()
{
	freopen("travela.in","r",stdin);
	freopen("travela.out","w",stdout);
	while(1)
	{
		scanf("%d%d%d",&n,&m,&k);
		if(n==0&&m==0&&k==0)break;
		vocaloid();
		shit();
	}
	return 0;
}