记录编号	35717	评测结果	AAAAAAAAAA
题目名称	冲浪	最终得分	100
用户昵称	Citron酱	是否通过	通过
代码语言	C++	运行时间	0.611 s
提交时间	2012-02-29 16:50:30	内存使用	4.65 MiB

#include <cstdio>

#define I_F "slide.in"
#define O_F "slide.out"

const long Maxn=50000;
const short Maxk=10;

struct edges
{
	long x,s;
	edges *next;
}*e[Maxn]={NULL};
long n;
short k;
long long f[Maxn][Maxk+1];

void Input();
template <typename Any>
inline Any Min(const Any&, const Any&);
template <typename Any>
inline Any Max(const Any&, const Any&);
long long Search(const long, const long);
void Output();

int main()
{
	Input();
	Output(); 
	return 0;
}

void Input()
{
	long m,a,b,c;
	edges *t;
	freopen(I_F,"r",stdin);
	scanf("%ld%ld%hd",&n,&m,&k);
	for (long i=0; i<m; i++)
	{
		scanf("%ld%ld%ld",&a,&b,&c);
		--a, --b;
		t=e[a];
		e[a]=new edges;
		e[a]->x=b;
		e[a]->s=c;
		e[a]->next=t;
	}
}

template <typename Any>
inline Any Min(const Any &a, const Any &b)
{
	return (a<b)?a:b;
}

template <typename Any>
inline Any Max(const Any &a, const Any &b)
{
	return (a>b)?a:b;
}

long long Search(const long a, const long b)
{
	if (f[a][b]==0)
	{
		for (edges *i=e[a]; i!=NULL; i=i->next)
			f[a][b]=Max(f[a][b],Search(i->x,b)+i->s);
		if (b>0)
			for (edges *i=e[a]; i!=NULL; i=i->next)
				f[a][b]=Min(f[a][b],Search(i->x,b-1)+i->s);
	}
	return f[a][b];
}

void Output()
{
	freopen(O_F,"w",stdout);
	printf("%lld",Search(0,k));
}