记录编号	132139	评测结果	AAAAAAAAAA
题目名称	[Tyvj Feb11] GF打dota	最终得分	100
用户昵称	奶猹	是否通过	通过
代码语言	C++	运行时间	0.112 s
提交时间	2014-10-25 15:01:39	内存使用	2.73 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<string>
#include<cmath>
#include<climits>
#include<queue>
#include<algorithm>
using namespace std;

int n,m;
int st,en,k;
struct aaa{
	int next;
	int to;
	int data;
}a[200001];
struct bbb{
	int g,h;
	int to;
	bool operator<(const bbb &b)const
	{return b.h+b.g<h+g;}
};
int tot=0;
int head[10001];
int dis[10001];
bool b[10001];
int views[10001];
int ans=0;

inline void init();
inline void work();
inline void outit();
inline void insert(int ,int ,int );
inline void spfa(int );
inline int Astar(int );

int main()
{
	freopen("dota.in","r",stdin);
	freopen("dota.out","w",stdout);
	init();
	work();
	outit();
	//while(1);
	return 0;
}
void init()
{
	scanf("%d%d",&n,&m);
    int x,y,z;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&x,&y,&z);
        insert(x,y,z);
        insert(y,x,z);
    }
    st=1;
    en=n;
    //scanf("%d%d%d",&st,&en,&k);
}
void work()
{
    spfa(1);
    int x;
    scanf("%d",&x);
    if(x==1)k=2;
    else
    {
		ans=dis[n];
		//for(int i=1;i<=n;i++)cout<<dis[i]<<' ';
		//cout<<endl;
		return ;
	}
    ans=Astar(k);
}
void outit()
{
	printf("%d\n",ans);
}

inline void spfa(int x)
{
    memset(dis,0x3f,sizeof(dis));
    queue<int> q;
    q.push(x);
    b[x]=1;
	dis[x]=0;
    int i,k0,t;
    while(!q.empty())
    {
        k0=q.front();
        q.pop();
        for(i=head[k0];i!=0;i=a[i].next)//
        {
            t=a[i].to;
            if(dis[t]>dis[k0]+a[i].data)
            {
                dis[t]=dis[k0]+a[i].data;
                if(!b[t])
                {
                    b[t]=1;
                    q.push(t);
                }
            }
        }
        b[k0]=0;
    }
}
inline int Astar(int x)
{
	bbb now,next;
	priority_queue<bbb> note;
	memset(views,0,sizeof(views));
	now.to=st;
	now.g=0;
	now.h=dis[st];
	note.push(now);
	while(!note.empty())
	{
		now=note.top();
		note.pop();
		views[now.to]++;
		if(views[now.to]>k)continue;
		if(views[en]==k)return now.g;
		for(int i=head[now.to];i!=0;i=a[i].next)
		{
			int t=a[i].to;
			next.to=t;
			next.g=now.g+a[i].data;
			next.h=dis[t];
			note.push(next);
		}
	}
	return -1;
}
inline void insert(int x,int y,int z)
{
        tot++;
        a[tot].to=y;
        a[tot].next=head[x];
        a[tot].data=z;
        head[x]=tot;
        tot++;
}