记录编号	24898	评测结果	AAAAAAAAAA
题目名称	冲浪	最终得分	100
用户昵称	Pom	是否通过	通过
代码语言	C++	运行时间	1.061 s
提交时间	2011-05-23 09:14:03	内存使用	10.56 MiB

#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>

using namespace std;

const int MAXN=60000;
const int MAXM=320000;
const int M=MAXN*12-10;
const long long oo=100000000000000LL;

struct edge
{
	int t,c;
	edge *p;
}e[MAXM],*v[MAXN];

int es=-1,n,m,i,j,k,K;
long long d[MAXN],ans=oo,f[MAXN][13];

inline void addedge(int i,int j,int c)
{
	e[++es].t=j; e[es].c=c; e[es].p=v[i]; v[i]=e+es;
}

void dfs(int u)
{
	if (d[u]!=-1) return;
	d[u]=0;
	for (edge *x=v[u];x;x=x->p)
	{
		dfs(x->t);
		if (d[u]<x->c+d[x->t]) d[u]=x->c+d[x->t];
	}
}

void dp(int u,int k)
{
	long long r1=0,r2=oo;
	if (f[u][k]!=-1) return;
	if (k==0) 
	{
		f[u][k]=d[u];
		return;
	}
	for (edge *x=v[u];x;x=x->p)
	{
		dp(x->t,k-1);
		dp(x->t,k);
		if (f[x->t][k]+x->c>r1) r1=f[x->t][k]+x->c;
		if (f[x->t][k-1]+x->c<r2) r2=f[x->t][k-1]+x->c;
	}
	f[u][k]=min(r1,r2);
}

int main()
{
	freopen("slide.in","r",stdin);
	freopen("slide.out","w",stdout);
	scanf("%d%d%d",&n,&m,&K);
	while (m--)
	{
		scanf("%d%d%d",&i,&j,&k);
		addedge(i,j,k);
	}
	for (i=1;i<=n;i++) d[i]=-1;
	dfs(1);
	for (i=1;i<=n;i++)
		for (j=0;j<=K;j++)
			f[i][j]=-1;
	dp(1,K);
	cout<<f[1][K]<<endl;
	return 0;
}