记录编号	173369	评测结果	AAAAAAAAAA
题目名称	[Tyvj Feb11] GF打dota	最终得分	100
用户昵称	forever	是否通过	通过
代码语言	C++	运行时间	0.125 s
提交时间	2015-07-28 17:22:54	内存使用	2.73 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<cstdlib>
using namespace std;
struct dd
{
	int zhong;
	int zhi;
	int next;
}jie[200002];
bool v[10002];
int ans=0;
int num[10002],tot,a,b,c,m,n,t;
int head[10002],dis[10002];
void add(int x,int y,int z)
{
	tot++;
	jie[tot].zhong=y;
	jie[tot].next=head[x];
	head[x]=tot;
	jie[tot].zhi=z;
	tot++;
}
struct data
{
	int g,h;
	int to;
	bool operator<(const data & ui) const
	{
		return ui.g+ui.h<g+h;
	}
};
void spfa()
{
	for(int i=1;i<=n;++i)
	   dis[i]=99999999;
	queue<int>q;
	dis[1]=0;
	v[1]=1;
	q.push(1);
	while(!q.empty())
	{
		int yu=q.front();
		q.pop();
		for(int i=head[yu];i;i=jie[i].next)
		{
			int lin=jie[i].zhong;
			if(dis[lin]>dis[yu]+jie[i].zhi)
			{
				dis[lin]=dis[yu]+jie[i].zhi;
				if(!v[lin])
				{
					v[lin]=1;
					q.push(lin);
				}
			}
		}
		v[yu]=0;
	}
}
int work(int k)
{
	data ser,next;
	priority_queue<data> po;
	memset(num,0,sizeof(num));
	ser.g=0;
	ser.to=1;
	ser.h=dis[n];
	po.push(ser);
	while(!po.empty())
	{
		ser=po.top();
		po.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;
			next.g=ser.g+jie[i].zhi;
			next.h=dis[yu];
			next.to=yu;
			po.push(next);
		}
	}
	 return -1;
}
int main()
{   freopen("dota.in","r",stdin);
    freopen("dota.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;++i)
	{
		scanf("%d%d%d",&a,&b,&c);
		add(a,b,c);
		add(b,a,c);
	}
	scanf("%d",&t);
	spfa();
	if(!t) 
	{   ans=dis[n];
		printf("%d",dis[n]);
	}
	else
	{
		ans=work(2);
		printf("%d",ans);
	}
	//return 0;
}