记录编号	502992	评测结果	AAAAAAAAAA
题目名称	[USACO Mar08] 牛跑步	最终得分	100
用户昵称	AntiLeaf	是否通过	通过
代码语言	C++	运行时间	0.018 s
提交时间	2018-07-30 19:12:08	内存使用	6.21 MiB

#include<bits/stdc++.h>
using namespace std;
const int maxn=1005,maxe=10005,maxm=maxe*30;
struct A{
	int x,d;
	A(int x,int d):x(x),d(d){}
	bool operator<(const A &a)const{return d>a.d;}
};
struct node{
	int w,i,d;
	node *lc,*rc;
	node(){}
	node(int w,int i):w(w),i(i),d(0){}
	void refresh(){d=rc->d+1;}
}null[maxm],*ptr=null,*root[maxn];
struct B{
	int x,w;
	node *rt;
	B(int x,node *rt,int w):x(x),w(w),rt(rt){}
	bool operator<(const B &a)const{return w+rt->w>a.w+a.rt->w;}
};
void Dijkstra();
void dfs(int);
node *newnode(int,int);
node *merge(node*,node*);
vector<int>G[maxn],W[maxn],id[maxn];
bool vis[maxn],used[maxe];
int u[maxe],v[maxe],w[maxe];
int d[maxn],p[maxn];
int n,m,k,s,t;
int main(){
	freopen("cowjog.in","r",stdin);
	freopen("cowjog.out","w",stdout);
	scanf("%d%d%d",&n,&m,&k);
	s=n;
	t=1;
	for(int i=0;i<=n;i++)root[i]=null;
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&u[i],&v[i],&w[i]);
		G[v[i]].push_back(u[i]);
		W[v[i]].push_back(w[i]);
		id[v[i]].push_back(i);
	}
	Dijkstra();
	for(int i=1;i<=n;i++){
		G[i].clear();
		W[i].clear();
		id[i].clear();
	}
	for(int i=1;i<=n;i++)
		if(p[i]){
			used[p[i]]=true;
			G[v[p[i]]].push_back(i);
		}
	for(int i=1;i<=m;i++){
		w[i]-=d[u[i]]-d[v[i]];
		if(!used[i])
			root[u[i]]=merge(root[u[i]],newnode(w[i],i));
	}
	dfs(t);
	priority_queue<B>heap;
	heap.push(B(s,root[s],0));
	printf("%d\n",d[s]);
	while(--k){
		if(heap.empty())printf("-1\n");
		else{
			int x=heap.top().x,w=heap.top().w;
			node *rt=heap.top().rt;
			heap.pop();
			printf("%d\n",d[s]+w+rt->w);
			if(rt->lc!=null||rt->rc!=null)
				heap.push(B(x,merge(rt->lc,rt->rc),w));
			if(root[v[rt->i]]!=null)
				heap.push(B(v[rt->i],root[v[rt->i]],w+rt->w));
		}
	}
	return 0;
}
void Dijkstra(){
	memset(d,63,sizeof(d));
	d[t]=0;
	priority_queue<A>heap;
	heap.push(A(t,0));
	while(!heap.empty()){
		int x=heap.top().x;
		heap.pop();
		if(vis[x])continue;
		vis[x]=true;
		for(int i=0;i<(int)G[x].size();i++)
			if(!vis[G[x][i]]&&d[G[x][i]]>d[x]+W[x][i]){
				d[G[x][i]]=d[x]+W[x][i];
				p[G[x][i]]=id[x][i];
				heap.push(A(G[x][i],d[G[x][i]]));
			}
	}
}
void dfs(int x){
	root[x]=merge(root[x],root[v[p[x]]]);
	for(int i=0;i<(int)G[x].size();i++)
		dfs(G[x][i]);
}
node *newnode(int w,int i){
	*++ptr=node(w,i);
	ptr->lc=ptr->rc=null;
	return ptr;
}
node *merge(node *x,node *y){
	if(x==null)return y;
	if(y==null)return x;
	if(x->w>y->w)swap(x,y);
	node *z=newnode(x->w,x->i);
	z->lc=x->lc;
	z->rc=merge(x->rc,y);
	if(z->lc->d>z->rc->d)swap(z->lc,z->rc);
	z->refresh();
	return z;
}