记录编号	24673	评测结果	AAAAAAAAAA
题目名称	冲浪	最终得分	100
用户昵称	苏轼	是否通过	通过
代码语言	C++	运行时间	0.620 s
提交时间	2011-04-14 12:05:55	内存使用	9.65 MiB

#include <cstdio>
#include <iostream>
using namespace std;
typedef long long s64;

const int MAXN=50005,MAXM=150005,MAXK=15;
const s64 oo=~0ull>>2;

struct Node
{
	int v,w;
	Node *next;
	Node(int _v,int _w,Node *_next):
		v(_v),w(_w),next(_next){}
	Node(){}
	void *operator new (size_t,void *p){return p;}
}*adj[MAXN],pool[MAXM*2],*mem=pool;
	
inline void addedge(int u,int v,int w)
{
	adj[u]=new (mem++)Node(v,w,adj[u]);
}

int N,M,K;
bool vis[MAXN];
s64 d[MAXN][MAXK];
void dp(int u)
{
	vis[u]=true;
	if (adj[u]==NULL)
	{
		for(int j=0;j<=K;j++)
			d[u][j]=0;
		return ;
	}
	d[u][0]=0;
	for(int i=1;i<=K;i++)
		d[u][i]=oo;
	for(Node *p=adj[u];p;p=p->next)
	{
		if (!vis[p->v])
			dp(p->v);
		for(int j=1;j<=K;j++)
			if (d[u][j]>d[p->v][j-1]+p->w)
				d[u][j]=d[p->v][j-1]+p->w;
		if (d[u][0]<d[p->v][0]+p->w)
			d[u][0]=d[p->v][0]+p->w;
	}
}

int main()
{
	freopen("slide.in","r",stdin);
	freopen("slide.out","w",stdout);
	scanf("%d%d%d",&N,&M,&K);
	for(int i=0;i<M;i++)
	{
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		addedge(u,v,w);
	}
	dp(1);
	cout<<d[1][K]<<endl;
	return 0;
}