记录编号	398960	评测结果	AAAAAAAAAA
题目名称	[Tyvj Feb11] GF打dota	最终得分	100
用户昵称	Hallmeow	是否通过	通过
代码语言	C++	运行时间	0.122 s
提交时间	2017-04-24 16:15:56	内存使用	7.94 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
int n,m;
#define pos(i,a,b) for(int i=(a);i<=(b);i++)
#define N 200000
#define INF 0x7fffffff
struct haha
{
       int to,w,next;
};
haha edge1[N],edge2[N];
int head1[N],head2[N];
int cnt1=1,cnt2=1;
int dis[N];
void add2(int u,int v,int w)
{
     edge2[cnt2].w=w;
     edge2[cnt2].to=v;
     edge2[cnt2].next=head2[u];
     head2[u]=cnt2++;
}
void add1(int u,int v,int w)
{
     edge1[cnt1].w=w;
     edge1[cnt1].to=v;
     edge1[cnt1].next=head1[u];
     head1[u]=cnt1++;
}
int flag[N];
void spfa(int x)
{
     memset(dis,0x3f,sizeof(dis));
     queue<int> q;
     flag[x]=1;
     dis[x]=0;
     q.push(x);
     while(!q.empty())
     {
         int i=q.front();
         for(int v=head2[i];v;v=edge2[v].next)
         {
             int j=edge2[v].to;
             if(dis[j]>dis[i]+edge2[v].w)
             {
               dis[j]=dis[i]+edge2[v].w;
               if(!flag[j])
               {
                   flag[j]=1;
                   q.push(j);
               }
             }
         }
         flag[q.front()]=0;
         q.pop();
     }
}
struct node2
{
       int g,f,to;
       bool operator<(const node2 &r )const
       {
            if(r.f==f)
             return r.g<g;
            return r.f<f;
       }
};
int astar(int s,int t,int k)
{
    node2 e,ne;
    int cnt=0;
    priority_queue<node2> Q;
    if(s==t)
      k++;
    if(dis[s]>1000000)
      return -1;
    e.to=s;e.g=0;e.f=e.g+dis[e.to];
    Q.push(e);
    while(!Q.empty())
    {
       e=Q.top();
       Q.pop();
       if(e.to==t)
         cnt++;
       if(cnt==k)
         return e.g;
       for(int i=head1[e.to];i;i=edge1[i].next)
       {
         ne.to=edge1[i].to;
         ne.g=e.g+edge1[i].w;
         ne.f=ne.g+dis[ne.to];
         Q.push(ne);
       }
    }
    return -1;
}
int main()
{
    freopen("dota.in","r",stdin);
    freopen("dota.out","w",stdout);
    cin>>n>>m;
    pos(i,1,m)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        add2(x,y,z);
        add2(y,x,z);
        add1(x,y,z);
        add1(y,x,z);
    }
    spfa(n);
    int p;
    cin>>p;
    if(p==0)
      printf("%d",dis[1]);
    else
        printf("%d",astar(1,n,2));
    //while(1);
    return 0;
}