堆优化的最短路径,其实可以用SPFA做的,效果会相当会
//堆优化的最短路径不知道什么原因的AC

#include 
<stdio.h>

const int MAX_N = 30005;

const int MAX_M = 150005;

const int MAX = 0x7fffffff;


//邻接链表部分
struct
{
    
int next;
    
int last;
}
head[MAX_N];

struct
{
    
int val;
    
int len;
    
int next;
}
point[MAX_M];
int now;

void initm ( int n )
{
    
    now 
= 0;
    
for ( int i=0; i<n; i++ )
    
{
        head[i].next 
= head[i].last = -1;
    }

}


void add ( int a, int b, int l )
{
    
    point[now].val 
= b;
    point[now].len 
= l;
    point[now].next 
= -1;
    
if ( head[a].next == -1 )
    
{
        head[a].next 
= now;
    }

    
else
    
{
        point[ head[a].last ].next 
= now;
    }

    head[a].last 
= now ++;
}


//堆部分
typedef struct
{
    
int val;
    
int addr;
}
type;
type heap[MAX_N];
int hnow;

int hash[MAX_N];//记录元素在堆中的位置

void inith ()//初始化堆
{
    
    hnow 
= 0;
}


void swap ( type *a, type *b )//交换堆中元素
{
    type temp;
    temp.addr 
= a->addr;
    temp.val 
= a->val;
    a
->addr = b->addr;
    a
->val = b->val;
    b
->addr = temp.addr;
    b
->val = temp.val;
}


void cpy ( type *a, type *b )//复制
{
    
    a
->addr = b->addr;
    a
->val = b->val;
}


void done ( int p )//调整堆向上
{
    
    
int fa;
    
while ( 1 )
    
{
        
if ( p & 1 )
        
{
            fa 
= p / 2;
        }

        
else
        
{
            fa 
= (p - 1/ 2;
        }

        
        
if ( p == 0 || heap[p].val > heap[fa].val )
        
{
            
return;
        }


        hash[ heap[p].addr ] 
= fa;
        hash[ heap[fa].addr ] 
= p;
        swap ( 
&heap[p], &heap[fa] );

        p 
= fa;
    }

}


void ins ( type *in )//插入
{
    hash[ in
->addr ] = hnow;
    cpy ( 
&heap[hnow], in );
    
int p = hnow ++;
    done ( p );
}


void del ( int p )
{

    hash[ heap[hnow
-1].addr ] = p;
    cpy ( 
&heap[p], &heap[hnow-1] );
    hnow 
--;

    
int ls, rs;
    
int flag = 1;
    
while ( flag )
    
{
        flag 
= 0;
        ls 
= p * 2 + 1;
        rs 
= p * 2 + 2;
        
if ( ls < hnow && rs < hnow )
        
{
            
if ( heap[ls].val < heap[rs].val && heap[ls].val < heap[p].val )
            
{
                hash[ heap[p].addr ] 
= ls;
                hash[ heap[ls].addr ] 
= p;
                swap ( 
&heap[p], &heap[ls] );
                p 
= ls;
                flag 
= 1;
            }

            
else if ( heap[rs].val < heap[ls].val && heap[rs].val < heap[p].val )
            
{
                hash[ heap[p].addr ] 
= rs;
                hash[ heap[rs].addr ] 
= p;
                swap ( 
&heap[p], &heap[rs] );
                p 
= rs;
                flag 
= 1;
            }

        }

        
else if ( ls < hnow  && rs >= hnow )
        
{
            
if ( heap[ls].val < heap[p].val )
            
{
                hash[ heap[p].addr ] 
= ls;
                hash[ heap[ls].addr ] 
= p;
                swap ( 
&heap[p], &heap[ls] );
                p 
= ls;
                flag 
= 1;
            }

        }

    }

}


//最短路径部分

int used[MAX_N];

void initdj ( int s, int n )
{

    
for ( int i=0; i<n; i++ )
    
{
        used[i] 
= 0;
    }

}


int dj ( int s, int t, int n )
{

    initdj ( s, n );
    
int next;
    
    inith ();
    
for ( int i=0; i<n; i++ )
    
{
        type in;
        
if ( i != s )
        
{
            in.addr 
= i;
            in.val 
= MAX;
        }

        
else
        
{
            in.addr 
= i;
            in.val 
= 0;
        }

        ins ( 
&in );
    }


    
for ( int i=0; i<n; i++ )
    
{
        next 
= heap[0].addr;
        used[ heap[
0].addr ] = 1;
        
int dis = heap[0].val;
        
if ( next == t )
        
{
            
break;
        }

        del ( 
0 );

        
for ( int j=head[next].next; j!=-1; j=point[j].next )
        
{
            
if ( ! used[ point[j].val ] )
            
{
                
if ( heap[ hash[ point[j].val ] ].val > dis + point[j].len )
                
{
                    heap[ hash[ point[j].val ] ].val 
= dis + point[j].len;
                    done ( hash[ point[j].val ] );
                }

            }

        }

    }

    
return heap[0].val;
}


int main ()
{

    
int n, m;
    
int b, e, l;

    
while ( scanf ( "%d%d"&n, &m ) != EOF )
    
{
        initm ( n );
        
for ( int i=0; i<m; i++ )
        
{
            scanf ( 
"%d%d%d"&b, &e, &l );
            add ( b
-1, e-1, l );
        }

        printf ( 
"%d\n", dj ( 0, n-1, n ) );
    }

    
return 0;
}