记录编号	502501	评测结果	AAAAAAAAAA
题目名称	[Tyvj Feb11] GF打dota	最终得分	100
用户昵称	6666	是否通过	通过
代码语言	C++	运行时间	0.108 s
提交时间	2018-07-27 10:53:11	内存使用	0.58 MiB

//
//  astar.cpp
//  
//
//  Created by apple on 2018/7/27.
//

#include <stdio.h>
#include <string.h>
#include <vector>
#include <queue>
using namespace std;
const int maxn=10005;
int n,m,dis[maxn];vector<int>son[maxn],v[maxn];
void Set(int prt,int to,int d){
    son[prt].push_back(to),v[prt].push_back(d);
}
bool bein[maxn];queue<int>q;
void Spfa(int S){
    memset(dis,0x3f,sizeof(dis));
    dis[S]=0,q.push(S),bein[S]=true;
    while(!q.empty()){
        int rt=q.front();q.pop(),bein[rt]=false;
        for(int i=0;i<son[rt].size();i++){
            int to=son[rt][i];
            if(dis[to]>dis[rt]+v[rt][i]){
                dis[to]=dis[rt]+v[rt][i];
                if(!bein[to])bein[to]=true,q.push(to);
            }
        }
    }
}
struct Node {
    int x,d;
    bool operator < (const Node &a)const{
        return d+dis[x]>a.d+dis[a.x];
    }
};priority_queue<Node>Q;
int Astar(int S,int T){
    Q.push((Node){S,0});
    while(!Q.empty()){
        Node prt=Q.top();Q.pop();int rt=prt.x;
        if(rt==T&&prt.d>dis[S])return prt.d;
        for(int i=0;i<son[rt].size();i++)
            Q.push((Node){son[rt][i],prt.d+v[rt][i]});
    }
}
int main(){
    freopen("dota.in","r",stdin);freopen("dota.out","w",stdout);
    scanf("%d%d",&n,&m);int p,x,y,z;
    while(m--)scanf("%d%d%d",&x,&y,&z),Set(x,y,z),Set(y,x,z);
    Spfa(n);scanf("%d",&p);
    if(p==0)printf("%d\n",dis[1]);
    else printf("%d\n",Astar(1,n));
}