记录编号	369709	评测结果	AAAAAAAAAA
题目名称	[USACO Mar08] 牛跑步	最终得分	100
用户昵称	WildRage	是否通过	通过
代码语言	C++	运行时间	0.041 s
提交时间	2017-02-10 15:04:34	内存使用	0.56 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
struct edge{
	int END,v,next;
}ZHENG[10005],FAN[10005];
struct A{
	int END,f,g;
	bool operator < (const A &a)const{
		if(f==a.f) return a.g<g;
		return a.f<f;
	} 
};
int first_zheng[1005],first_fan[1005],p;
int dis[1005];
int n;
int s;
void add(int a,int b,int c);
void spfa(int a);
int Astar(int k);
int main()
{
	freopen("cowjog.in","r",stdin);
	freopen("cowjog.out","w",stdout);
	//cin>>n>>m;
	memset(first_fan,-1,sizeof(first_fan));
	memset(first_zheng,-1,sizeof(first_zheng));
	p=1;
	int m,a,b,c,K;
	scanf("%d%d%d",&n,&m,&K);
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&a,&b,&c);
		if(a>b) add(a,b,c);
		else add(b,a,c);
	}
	spfa(1);
	for(int k=1;k<=K;k++){
		s=0;
		cout<<Astar(k)<<endl;
	}
	//while(1);
}
void add(int a,int b,int c){
	ZHENG[p].END=b;
	ZHENG[p].v=c;
	ZHENG[p].next=first_zheng[a];
	FAN[p].END=a;
	FAN[p].v=c;
	FAN[p].next=first_fan[b];
	first_zheng[a]=p;
	first_fan[b]=p++;
}
void spfa(int a){
	memset(dis,0x3f,sizeof(dis));
	dis[a]=0;
	bool flag[1005]={0};
	queue<int> p;
	p.push(a);
	flag[a]=1;
	while(!p.empty()){
		int tmp=p.front();
		flag[tmp]=0;
		p.pop();
		for(int i=first_fan[tmp];i!=-1;i=FAN[i].next){
			if(dis[FAN[i].END]>dis[tmp]+FAN[i].v){
				dis[FAN[i].END]=dis[tmp]+FAN[i].v;
				if(!flag[FAN[i].END]){
					flag[FAN[i].END]=1;
					p.push(FAN[i].END);
				}
			}
		}
	}
}
int Astar(int k){
	priority_queue<A> p;
	A s1,s2;
	s1.END=n;s1.g=0;
	s1.f=s1.g+dis[n];
	p.push(s1);
	while(!p.empty()){
		s2=p.top();
		p.pop();
		if(s2.END==1){
			s++;
			if(s==k) return s2.g;
		}
		for(int i=first_zheng[s2.END];i!=-1;i=ZHENG[i].next){
			s1.END=ZHENG[i].END;
			s1.g=s2.g+ZHENG[i].v;
			s1.f=s1.g+dis[ZHENG[i].END];
			p.push(s1);
		}
	}
	return -1;
}