记录编号	270637	评测结果	AAAAAAAAAA
题目名称	[Tyvj Feb11] GF打dota	最终得分	100
用户昵称	洛克索耶夫	是否通过	通过
代码语言	C++	运行时间	0.063 s
提交时间	2016-06-15 09:35:49	内存使用	2.91 MiB

#include<bits/stdc++.h>
using namespace std;

int Read()
{
	int a = 0, minus = 1;
	char ch = getchar();
	if(ch == '-')       minus = -1;
	while(ch < '0' || ch > '9'){
		ch = getchar();
		if(ch == '-')	minus = -1;
	}
	while(ch >= '0' && ch <= '9'){
		a = a * 10 + ch - '0';
		ch = getchar();
	}
	return a * minus;
}

struct Node{
	int id;
	int f, g, h;
	Node()
	{
		id = f = g = h = 0;
	}
	Node(int x, int y)
	{
		id = x; f = y;
	}
	Node(int a, int b, int c)
	{
		id = a; g = b; h = c;
		f = g + h;
	}
	bool operator < (const Node& a)const{
		return f > a.f;
	} 
};

struct EDGE{
	int to, next, w;
	EDGE()
	{
		to = next = w;
	}
}edges[110000];

int dis[10010], from[110000], to[110000], w[110000];
int head[10010], tot, n, m, p;

void AddEdge(int from, int to, int w)
{
	edges[++tot].to = to;
	edges[tot].w = w;
	edges[tot].next = head[from];
	head[from] = tot;
}

void ReBuild()
{
	memset(head, 0, sizeof(head));
	tot = 0;
	for(int i = 1; i <= m; i++){
		AddEdge(to[i], from[i], w[i]);
		AddEdge(from[i], to[i], w[i]); 
	}
}

void DJS(int a)
{
	memset(dis, 0x7f, sizeof(dis));
	dis[a] = 0;
	priority_queue <Node> Q;
	Q.push(Node(a, 0));
	while(!Q.empty()){
		Node top = Q.top(); Q.pop();
		int num = top.id;
		if(dis[num] != top.f)	continue;
		for(int i = head[num]; i; i = edges[i].next){
			int to = edges[i].to;
			if(dis[num] + edges[i].w < dis[to]){
				dis[to] = dis[num] + edges[i].w;
				Q.push(Node(to, dis[to]));
			}
		}
	}
	//for(int i = 1; i <= n; i++)	printf("%d ", dis[i]);
}

void AStar(int s, int t, int k)
{
	DJS(t);
	ReBuild();
	priority_queue <Node> Q;
	Q.push(Node(s, 0, dis[s]));
	while(!Q.empty()){
		Node top = Q.top();Q.pop();
		if(top.id == t){
			if(k == 1)	printf("%d", top.g);
			k--;
			if(k == 0)	return;
		}
		for(int i = head[top.id]; i; i = edges[i].next){
			int to = edges[i].to;
			Q.push(Node(to, top.g + edges[i].w, dis[to]));
		}
	}
}

int main()
{
	freopen("dota.in", "r", stdin);freopen("dota.out", "w", stdout);
	n = Read(); m = Read();
	for(int i = 1; i <= m; i++){
		from[i] = Read(), to[i] = Read(), w[i] = Read();
		AddEdge(from[i], to[i], w[i]);
		AddEdge(to[i], from[i], w[i]);
	}
	p = Read();
	if(p == 0)	AStar(1, n, 1);
	else AStar(1, n, 2);
	fclose(stdin);
	fclose(stdout);
	return 0;
}
/*
5 8
5 4 1
5 3 1
5 2 1
5 1 1
4 3 4
3 1 1
3 2 1
2 1 1
1
*/