记录编号	49618	评测结果	AAAAAAAAAA
题目名称	旅行	最终得分	100
用户昵称	Truth.Cirno	是否通过	通过
代码语言	C++	运行时间	0.104 s
提交时间	2012-11-08 17:24:35	内存使用	3.33 MiB

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <memory.h>
#include <stack>
#include <queue>
using namespace std;

int n,timnow,map[110][110],dad[110],siz[110],tim[110],timlow[110],dist[110][15];
bool insta[110],inque[110],used[110];
stack<int> sta,sta2;
queue<int> que,empty;

int findroot(int ys)
{
	while (dad[ys])
	{
		sta2.push(ys);
		ys=dad[ys];
	}
	while (!sta2.empty())
	{
		dad[sta2.top()]=ys;
		sta2.pop();
	}
	return(ys);
}

void combine(int a,int b)
{
	a=findroot(a);
	b=findroot(b);
	if (a==b)
		return;
	if (siz[a]>siz[b])
	{
		siz[a]+=siz[b];
		dad[b]=a;
	}
	else
	{
		siz[b]+=siz[a];
		dad[a]=b;
	}
}

void tarjan(int pos)
{
	int i;
	timnow++;
	tim[pos]=timnow;
	timlow[pos]=timnow;
	sta.push(pos);
	insta[pos]=true;
	used[pos]=true;
	for (i=1;i<=n;i++)
	{
		if (pos!=i&&map[pos][i]<100000000)
		{
			if (!used[i])
			{
				tarjan(i);
				timlow[pos]=min(timlow[pos],timlow[i]);
			}
			else if (insta[i])
			{
				timlow[pos]=min(timlow[pos],tim[i]);
			}
		}
	}
	if (timlow[pos]==tim[pos])
		while (!sta.empty())
		{
			i=sta.top();
			insta[i]=false;
			sta.pop();
			if (pos!=i)
				combine(pos,i);
			else
				break;
		}
}

int main(void)
{
	freopen("travela.in","r",stdin);
	freopen("travela.out","w",stdout);
	int i,j,m,k,from,to,cost;
	bool run;
	while (scanf("%d%d%d",&n,&m,&k)==3)
	{
		if (n==0&&m==0&&k==0)
			break;
		
		/*assign*/
		memset(used,0,sizeof(used));
		memset(inque,0,sizeof(inque));
		que=empty;
		timnow=0;
		for (i=1;i<=n;i++)
		{
			dad[i]=0;
			siz[i]=1;
			for (j=1;j<=n;j++)
			{
				if (i==j)
					map[i][j]=0;
				else
					map[i][j]=100000000;
			}
		}
		for (i=1;i<=n;i++)
			for (j=0;j<=k;j++)
				dist[i][j]=100000000;
		/*assign*/
		
		for (i=1;i<=m;i++)
		{
			cin>>from>>to>>cost;
			from++;
			to++;
			map[from][to]=min(map[from][to],cost);
		}
		tarjan(0);
		
		/*spfa*/
		dist[1][0]=0;
		inque[1]=true;
		que.push(1);
		while (!que.empty())
		{
			from=que.front();
			for (to=1;to<=n;to++)
				if (from!=to&&map[from][to]<100000000)
				{
					run=false;
					if (findroot(from)==findroot(to))
					{
						for (i=0;i<=k;i++)
						{
							if (dist[to][i]>dist[from][i]+map[from][to])
							{
								dist[to][i]=dist[from][i]+map[from][to];
								run=true;
							}
						}
					}
					else
					{
						for (i=1;i<=k;i++)
						{
							if (dist[to][i]>dist[from][i-1]+2*map[from][to])
							{
								dist[to][i]=dist[from][i-1]+2*map[from][to];
								run=true;
							}
						}
					}
					if (run)
					{
						if (!inque[to])
						{
							inque[to]=true;
							que.push(to);
						}
					}
				}
			inque[from]=false;
			que.pop();
		}
		/*spfa*/
		
		cost=100000000;
		for (i=0;i<=k;i++)
			cost=min(cost,dist[n][i]);
		if (cost==100000000)
			cout<<"-1\n";
		else
			cout<<cost<<endl;
	}
	return(0);
}