记录编号	390504	评测结果	AAAAAAAAAA
题目名称	[USACO Mar08] 牛跑步	最终得分	100
用户昵称	HZOI_蒟蒻一只	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2017-04-03 10:55:35	内存使用	0.00 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int maxn=1005,maxm=10005,maxk=105,inf=1000100000;
struct node{int next,to,wei;}edge[maxm],edge2[maxm];
struct Node{
	int num,dis,g,h;//g为实际已走距离，h为估计的距离 ，有向搜索 
	Node(){};
	Node(int a,int b){num=a;dis=b;}
	Node(int a,int b,int c){num=a;g=b;h=c;dis=g+h;}
	bool operator < (const Node & a)const{
		return dis>a.dis;
	} 
};
int n,m,head[maxn],dis[maxn],tot,k,x,y,z,len[maxk],cnt,scnt,
qt[maxn],head2[maxn];bool inq[maxn];
void addedge(int u,int v,int w)
{edge[cnt].to=v;edge[cnt].wei=w;edge[cnt].next=head[u];head[u]=cnt++;}
void addedge2(int u,int v,int w)
{edge2[scnt].to=v;edge2[scnt].wei=w;edge2[scnt].next=head2[u];head2[u]=scnt++;}
void spfa()
{
	queue<int>q;memset(dis,127/3,sizeof(dis));dis[1]=0;inq[1]=1;q.push(1);
	while(!q.empty()){int s=q.front();q.pop();inq[s]=0;
		for(int i=head2[s];i!=-1;i=edge2[i].next){int v=edge2[i].to;
			if(edge2[i].wei+dis[s]<dis[v]){dis[v]=dis[s]+edge2[i].wei;
				if(!inq[v]){inq[v]=1;q.push(v);}}}}
}
void astar()
{
	priority_queue<Node> q;
	q.push(Node(n,0,dis[n]));
	while(!q.empty()){
		Node temp=q.top();q.pop();
		if(temp.num==1){
			printf("%d\n",temp.g);
			k--;
			if(k==0)return;
		}
		for(int i=head[temp.num];i!=-1;i=edge[i].next){//从这个点进行扩展 
			q.push(Node(edge[i].to,edge[i].wei+temp.g,dis[edge[i].to]));
		}
	}
	for(int i=1;i<=k;i++)printf("-1\n");
}
int haha()
{
	freopen("cowjog.in","r",stdin);freopen("cowjog.out","w",stdout);
	scanf("%d%d%d",&n,&m,&k);
	memset(head,-1,sizeof(head));memset(head2,-1,sizeof(head2));
	for(int i=1;i<=m;i++){scanf("%d%d%d",&x,&y,&z);addedge(x,y,z);addedge2(y,x,z);}
	spfa();astar();
	//while(1);
}
int sb=haha();
int main(){;}