记录编号	270887	评测结果	AAAAAAAAAA
题目名称	[Tyvj Feb11] GF打dota	最终得分	100
用户昵称	哒哒哒哒哒！	是否通过	通过
代码语言	C++	运行时间	0.087 s
提交时间	2016-06-15 13:54:04	内存使用	14.05 MiB

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#define maxn 10010
#define maxe 1000010
using namespace std;
int n,m,q;
struct Edge{
	int to,next,w;
}e[maxe];
struct Node{
	int num,dist;
	int h,g;
	Node(int x,int y){
		num=x;dist=y;
	}
	Node(int x,int y,int z){
		num=x;g=y;h=z;
		dist=h+g;
	}
	bool operator <(const Node&A) const{
		return dist>A.dist;
	}
};
int tot,head[maxe];
int dis[maxn];
void Laddedge(int from,int to,int w)
{
	e[++tot].to=to;
	e[tot].w=w;
	e[tot].next=head[from];
	head[from]=tot;
}
void Ldijkstra(int begin)
{
	memset(dis,0x7f,sizeof(dis));
	priority_queue<Node> q;
	dis[begin]=0;
	q.push(Node(begin,0));
	while(!q.empty()){
		Node node=q.top();q.pop();
		int k=node.num;
		if(dis[k]!=node.dist) continue;
		for(int i=head[k];i;i=e[i].next){
			int to=e[i].to;
			if(dis[to]>dis[k]+e[i].w){
				dis[to]=dis[k]+e[i].w;
				q.push(Node(to,dis[to]));
			}
		}
	}
}
void Lastar(int s,int t,int k)
{
 
	priority_queue<Node> q;
	q.push(Node(s,0,dis[s]));
	while(!q.empty()){
		Node x=q.top();q.pop();
		int id=x.num;
	//	cout<<id<<endl;system("pause");
		if(id==t){
		//	cout<<x.g<<endl;system("pause");
			if(k==2){k--;continue;}	
			if(k==1&&x.g!=dis[1]){
				printf("%d",x.g);
				return;
			}
		}
		for(int i=head[id];i;i=e[i].next){
			int to=e[i].to;
			q.push(Node(to,x.g+e[i].w,dis[to]));
		}
	}
}
int main()
{
	freopen("dota.in","r",stdin);
	freopen("dota.out","w",stdout);
	scanf("%d%d",&n,&m);
	int x,y,w;
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&x,&y,&w);
		Laddedge(x,y,w);
		Laddedge(y,x,w);
	}
	Ldijkstra(n);
	scanf("%d",&q);
	if(q==0) printf("%d",dis[1]);
	else Lastar(1,n,2);
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}