记录编号	158693	评测结果	WWWWWWWWWW
题目名称	备用交换机	最终得分	0
用户昵称	Foenix	是否通过	未通过
代码语言	C++	运行时间	0.014 s
提交时间	2015-04-16 20:54:36	内存使用	2.28 MiB

#include <cstdio>
#include <queue>
using namespace std;
const int MAXM=150005,MAXN=30005,INF=(1<<29);

struct node{
	int pi,dist;
	bool operator <(const node &X)const{
		return dist>X.dist;
	}
}e;

struct NODE{
	int to,next,va;
}A[MAXM];


int len,n,m;
int head[MAXN],Dis[MAXN];
priority_queue<node>T;
bool v[MAXN];

void Add_edge(int a,int b,int c){
	len++; A[len].to=b; A[len].va=c; A[len].next=head[a]; head[a]=len;
}

void Init(){
	scanf("%d%d",&n,&m);
	int a,b,c;
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&a,&b,&c);
		Add_edge(a,b,c);
	}
}

void Chafen(){
	for(int i=1;i<=n;i++)Dis[i]=INF;
	Dis[1]=0; e.pi=1;e.dist=Dis[1];
	int tmp,y;	T.push(e);
	while(!T.empty()){
		while(!T.empty()&&v[T.top().pi]==1) T.pop();
		if(T.empty()) break;
		tmp=T.top().pi;v[tmp]=1;
		T.pop();
		for(int i=head[tmp];i;i=A[i].next){
			y=A[i].to;
			if(Dis[y]>Dis[tmp]+A[i].va){
				Dis[y]=Dis[tmp]+A[i].va;
				e.pi=y; e.dist=Dis[y];
				T.push(e);
			}
		}
	}
	printf("%d\n",Dis[n]);
}
int main(){
	freopen("gd.in","r",stdin);
	freopen("gd.out","w",stdout);
	Init();
	Chafen();
    return 0;
}