记录编号	175241	评测结果	AAAAAAAAAA
题目名称	[USACO Mar08] 牛跑步	最终得分	100
用户昵称	forever	是否通过	通过
代码语言	C++	运行时间	0.087 s
提交时间	2015-08-05 07:37:17	内存使用	0.56 MiB

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<queue>
#include<cstring>
using namespace std;
int a,b,c;
struct dd
{
	int zhong;
	int juli;
	int next;
}jie[10005],jiege[10005];
int head[1002],heard[1002],num[1002];
int tot,tot1,n,m,k,dis[1002];
bool v[1002];
struct data
{
	int g,h,to;
	bool operator<(const data  &a)const 
	{
		return a.g+a.h<g+h;
	}
};
void add(int x,int y,int r)
{
	tot++;
	jiege[tot].zhong=y;
	jiege[tot].juli=r;
	jiege[tot].next=heard[x];
	heard[x]=tot;
}
void add1(int x,int y,int r)
{
	tot1++;
	jie[tot1].juli=r;
	jie[tot1].next=head[x];
	jie[tot1].zhong=y;
	head[x]=tot1;
}
void spfa(int y)
{
	for(int i=1;i<=n;++i)
	   dis[i]=999999999;
	dis[y]=0;
	v[y]=1;
	queue<int>po;
	po.push(y);
	while(!po.empty())
	{
		int yu=po.front();
		po.pop();
		v[yu]=0;
		for(int i=heard[yu];i;i=jiege[i].next)
		{
			int lin=jiege[i].zhong;
			if(dis[yu]+jiege[i].juli<dis[lin])
			{
				dis[lin]=dis[yu]+jiege[i].juli;
				if(!v[lin])
				{
					v[lin]=1;
					po.push(lin);
				}
			}
		}
	}
	
}
int A_star(int k)
{
	data ser,hj;
	priority_queue<data>q;
	memset(num,0,sizeof(num));
	ser.g=0;
	ser.h=dis[1];
	ser.to=1;
	q.push(ser);
	while(!q.empty())
	{
		ser=q.top();
		q.pop();
		num[ser.to]++;
		if(num[ser.to]>k) continue;
		if(num[n]==k){
			return ser.g;
		}
		for(int i=head[ser.to];i;i=jie[i].next)
		{
			int yu=jie[i].zhong;
			hj.g=ser.g+jie[i].juli;
			hj.h=dis[yu];
			hj.to=yu;
			q.push(hj);
		}
	}
	return -1;
}
int main()
{   freopen("cowjog.in","r",stdin);
    freopen("cowjog.out","w",stdout);
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<=m;++i)
	{
		scanf("%d%d%d",&a,&b,&c);
		add(a,b,c);
		add1(b,a,c);
	}
	spfa(n);
	printf("%d\n",dis[1]);
	for(int i=2;i<=k;++i)
	{
		int ji=A_star(i);
		printf("%d\n",ji);
	}
}