记录编号	24668	评测结果	AAAAAAAAAA
题目名称	冲浪	最终得分	100
用户昵称	.Xmz	是否通过	通过
代码语言	C++	运行时间	0.995 s
提交时间	2011-04-14 11:52:52	内存使用	14.50 MiB

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

using namespace std;
const int maxm=355555;
const int maxn=55555;

int n,m,k,eh;
struct edge
{
	int t,c;
	edge *next;
}E[maxm],*V[maxn];
int ind[maxn];
inline void addedge(int a,int b,int c)
{
	E[++eh].next=V[a];  V[a]=E+eh;  V[a]->t=b; V[a]->c=c;
	ind[b]++;
}

void init()
{
	scanf("%d%d%d",&n,&m,&k);
	int a,b,c;
	for (;m;--m)
	{
		scanf("%d%d%d",&a,&b,&c);
		addedge(b,a,c);
	}
}

long long f[maxn][11];
long long g[maxn][11];
int x[maxn],xn;
int stack[maxn],sh;

void topsort()
{
	x[++xn]=n;
	stack[++sh]=n;
	while (sh!=0)
	{
		int u=stack[sh--];
		for (edge *e=V[u];e;e=e->next)
		{
			if (--ind[e->t]==0)
			{
				stack[++sh]=e->t;
				x[++xn]=e->t;
			}
		}
	}
}

long long lmin(long long a,long long b)
{
	if (a==-1) return b;
	if (b==-1) return a;
	else return a<b ? a : b;
}

void dp(int u)
{
	for (int i=0;i<=k;i++)
		f[u][i]=lmin(f[u][i],g[u][i]);
	for (edge *e=V[u];e;e=e->next)
	{
		int v=e->t;
		for (int i=0;i<=k;i++)
		if (f[u][i]!=-1)
		{
			f[v][i]=max(f[v][i],f[u][i]+e->c);
			if (i<k)
				g[v][i+1]=lmin(g[v][i+1],f[u][i]+e->c);
		}
	}
}

void solve()
{
	topsort();
	memset(g,-1,sizeof(g));
	f[n][0]=0;g[n][0]=0;
	for (int i=1;i<=n;i++)
		dp(x[i]);
	printf("%lld\n",f[1][k]);
}

int main()
{
	freopen("slide.in","r",stdin);
	freopen("slide.out","w",stdout);
	init();
	solve();
	return 0;
}