> #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;
> }
想WA就WA,WA得精彩

RP is Important