记录编号	100998	评测结果	AAAAAAAAAA
题目名称	旅行	最终得分	100
用户昵称	OI永别	是否通过	通过
代码语言	C++	运行时间	0.051 s
提交时间	2014-05-09 16:19:30	内存使用	1.88 MiB

#include<cstdio>
#include<cstring>
#include<iostream>
#include<stack>
using namespace std;
#define M 101000
#define N 110
#define K 15
#define qm 1510
#define pa pair <int, int>
#define fi first
#define se second
int n, m, k;
struct arr{
	int ff,tt,ww,next;
}c[M];
stack <int> S;
int low[N],dfn[N],id[N];
int dis[K][N];
bool v[N][K];
bool vis[N];
int r[N];
int tot = 0;
int sum = 0, num = 0;
pa q[qm + 1];
inline void add(int x, int y, int z){
	c[++tot].ff = x; c[tot].tt = y;
	c[tot].next = r[x]; r[x] = tot;
	c[tot].ww = z;	
}

void tarjan(int x){
	low[x] = dfn[x] = ++num;
	S.push(x);
	vis[x] = 1;
	for (int i = r[x]; i; i = c[i].next){
		int y = c[i].tt;
		if (!dfn[y]){
			tarjan(y);
			low[x] = min(low[x],low[y]);
		}
		else{
			if (vis[y]){
				low[x] = min(low[x], dfn[y]);
			}
		}
	}
	if (low[x] == dfn[x]){
		int y;
		sum ++;
		do{
			y = S.top();
			S.pop();
			id[y] = sum;
			vis[y] = 0;
		}while (x != y);
	}
	return;
}

void spfa(){
	memset(dis, 0x3f, sizeof(dis));
	memset(v, 0, sizeof(v));
	int h = 0, t = 0;
	for (int i = 0; i <= k; i ++) q[++t] = make_pair(1, i),dis[i][1] = 0;
	while (h != t){
		h = (h % qm) + 1;
		int x = q[h].fi, tim = q[h].se;
		v[x][tim] = 0;
		for (int i = r[x]; i; i = c[i].next){
			int y = c[i].tt;
			if (id[y] == id[x]){
				if (dis[tim][y] > dis[tim][x] + c[i].ww){
					dis[tim][y] = dis[tim][x] + c[i].ww;
					if (!v[y][tim]){
						v[y][tim] = 1;
						t = (t % qm) + 1;
						q[t] = make_pair(y, tim);
					}
				}
			}
			else{
				if (tim == k) continue;
				if (dis[tim + 1][y] > dis[tim][x] + 2 * c[i].ww){
					dis[tim + 1][y] = dis[tim][x] + 2 * c[i].ww;
					if (!v[y][tim + 1]){
						v[y][tim + 1] = 1;
						t = (t % qm) + 1;
						q[t] = make_pair(y, tim + 1);
					}
				}
			}
		}
	}
	return;
}

int main(){
	freopen("travela.in", "r", stdin);
	freopen("travela.out", "w", stdout);
	while (scanf("%d%d%d",&n, &m, &k), n || m || k){
		memset(r, 0, sizeof(r)); tot = 0;
		memset(c, 0, sizeof(c)); num = sum = 0;
		memset(dfn, 0, sizeof(dfn)); memset(low, 0, sizeof(low));
		while (S.size()) S.pop();
		int x, y, z;
		for (int i = 1; i <= m; i ++){
			scanf("%d%d%d",&x, &y, &z);
			x ++, y ++;
			add(x, y, z);
		}
		for (int i = 1; i <= n; i++){
			if (!dfn[i]) tarjan(i);
		}
		spfa();
		int ans = 0x3f3f3f3f;
		for (int i = 0; i <= k; i ++){
			ans = min(dis[i][n], ans);
		}
		if (ans == 0x3f3f3f3f) puts("-1");
		else printf("%d\n",ans);
	}
	return 0;
}