#include<cstdio>
const int maxn=30001, maxm=150002;
int n,m,E,d[maxn],first[maxn],next[maxm],point[maxm],value[maxm];
int len,heap[maxn],pla[maxn];
inline void Add_edge(int u,int v,int w){
	point[++E]=v;value[E]=w;next[E]=first[u];first[u]=E;
}
void swap(int a,int b){
	int t=heap[a];heap[a]=heap[b];heap[b]=t;
	pla[heap[a]]=a;pla[heap[b]]=b;
}
void up(int x){
	while(x>1&&d[heap[x]]<d[heap[x/2]])swap(x,x>>=1);
}
void down(int x){
	for(int min;x*2<=len;x=min){
		min=(x*2<len?(d[heap[x*2]]<d[heap[x*2+1]]?x*2:x*2+1):x*2);
		if(d[heap[min]]>=d[heap[x]])break;
		swap(x,min);
	}
}
int main(){
	//freopen("3159.in","rb",stdin);
	scanf("%d%d",&n,&m);
	for(int i=0,x,y,z;i<m;i++){
		scanf("%d%d%d",&x,&y,&z);
		Add_edge(x,y,z);
	}
	for(int i=2;i<=n;i++)d[i]=1061109567;
	for(int i=1;i<=n;i++)pla[heap[i]=i]=i;
	for(len=n;len;){
		int p=heap[1];
		swap(1,len--);
		down(1);
		for(int i=first[p];i;i=next[i])
			if(d[point[i]]>d[p]+value[i]){
				d[point[i]]=d[p]+value[i];
				up(pla[point[i]]);
			}
	}
	printf("%d\n",d[n]);
	return 0;
}

• 同请 (1194) shantingst 2010-11-15 18:52:58