记录编号	333823	评测结果	AAAAAAAAAA
题目名称	[USACO Mar08] 牛跑步	最终得分	100
用户昵称	traceback	是否通过	通过
代码语言	C++	运行时间	0.151 s
提交时间	2016-10-31 15:32:13	内存使用	0.40 MiB

#include <cstdio>
#include <queue>
#include <stack>
using namespace std;
priority_queue<int> que[1005];
int n,m,k,ind[1005];
int head[1005],sz=1;
struct E {
	int to,w,nxt;
}ed[10005];
void add_edge(int u,int v,int c) {
	ed[sz].to=v;
	ed[sz].w=c;
	ed[sz].nxt=head[u];
	head[u]=sz++;
}
stack<int> S;
int tmp[105],t=0;
void topo() {
	for (int i=1;i<=n;i++) if (!ind[i]) S.push(i);
	que[n].push(0);
	while (!S.empty()) {
		int v=S.top();S.pop();
		if (v==1) {
			break;
		}
		t=0;
		while (!que[v].empty()) {
			tmp[++t]=que[v].top();
			que[v].pop();
		}
		for (int i=head[v];i;i=ed[i].nxt) {
			int p=ed[i].to;
			for (int j=1;j<=t;j++) {
				que[p].push(ed[i].w+tmp[j]);
			}
			while (que[p].size()>k) {
				que[p].pop();
			}
			if (!--ind[p]) S.push(p);
		}
	}
	int r=k-que[1].size();
	t=0;
	while (!que[1].empty()) {
		tmp[++t]=que[1].top();
		que[1].pop();
	}
	while (t) {
		printf("%d\n",tmp[t--]);
	}
	for (int i=0;i<r;i++) printf("-1\n");
}
int main() {
	freopen("cowjog.in","r",stdin);
	freopen("cowjog.out","w",stdout);
	scanf("%d%d%d",&n,&m,&k);
	int a,b,c;
	for (int i=1;i<=m;i++) {
		scanf("%d%d%d",&a,&b,&c);
		add_edge(a,b,c);
		ind[b]++;
	}
	topo();
	return 0;
}