参考Roadblocks POJ - 3255：
洛谷P2865 [USACO06NOV]路障Roadblocks：
一、直接Dijkstra：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<map>
#include<queue>
#include<set>
#define ll long long
#define llu unsigned ll
using namespace std;
const int mod=1000000007;
const int maxn=200100;
const int maxx=5200;
const int inf=0x3f3f3f3f;
int head[maxx],edge[maxn],ver[maxn],nt[maxn];
int d1[maxx],d2[maxn];
int tot=1,n,m;


void add(int x,int y,int z)
{
    ver[++tot]=y,edge[tot]=z;
    nt[tot]=head[x],head[x]=tot;
}

int Dij(void)
{
    memset(d1,0x3f,sizeof(d1));
    memset(d2,0x3f,sizeof(d2));
    d1[1]=0;
    priority_queue<pair<int,int> >q;
    q.push(make_pair(0,1));

    while(q.size())
    {
        int x=q.top().second;
        int nowd=-q.top().first;
        //cout<<"x: "<<x<<" now: "<<nowd<<endl;
        q.pop();
        if(d2[x]<nowd) continue;
        for(int i=head[x];i;i=nt[i])
        {
            int y=ver[i],z=edge[i];
            int pm=nowd+z;
            if(d1[y]>pm)
            {
                swap(d1[y],pm);
                q.push(make_pair(-d1[y],y));
            }
            if(d1[y]<pm&&d2[y]>pm)
            {
                d2[y]=pm;
                q.push(make_pair(-d2[y],y));
            }
        }
    }
    return d2[n];
}


int main(void)
{
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        memset(head,0,sizeof(head));
        tot=1;
        int x,y,z;
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d%d",&x,&y,&z);
            add(x,y,z);
            add(y,x,z);
        }

        printf("%d\n",Dij());

    }


    return 0;
}

二、A*+Dijkstra:

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<map>
#include<queue>
#include<set>
#define ll long long
#define llu unsigned ll
using namespace std;
const int mod=1000000007;
const int maxn=200100;
const int maxx=5200;
const int inf=0x3f3f3f3f;
int head[maxx],edge[maxn],ver[maxn],nt[maxn];
int d[maxx];
bool ha[maxn];
int tot=1,n,m;


void add(int x,int y,int z)
{
    ver[++tot]=y,edge[tot]=z;
    nt[tot]=head[x],head[x]=tot;
}

struct node
{
    int x,dx,fx;
    node(){}
    node(int a,int b,int c)
    {
        x=a,dx=b,fx=c;
    }
    friend bool operator <(const node &a,const node &b)
    {
        return a.dx+a.fx>b.dx+b.fx;
    }
};

void Dij(void)
{
    memset(d,0x3f,sizeof(d));
    memset(ha,0,sizeof(ha));
    d[n]=0;
    priority_queue<pair<int,int> >q;
    q.push(make_pair(0,n));

    while(q.size())
    {
        int x=q.top().second;
        q.pop();
        if(ha[x]) continue;
        ha[x]=true;

        for(int i=head[x];i;i=nt[i])
        {
            int y=ver[i],z=edge[i];
            if(d[y]>d[x]+z)
            {
                d[y]=d[x]+z;
                q.push(make_pair(-d[y],y));
            }
        }
    }
    return ;
}

int s2(void)
{
    int sum=0;
    int cnt=0;
    priority_queue<node>q;
    q.push(node(1,0,d[1]));

    while(q.size())
    {
        node now=q.top();
        q.pop();
        if(sum==0&&now.x==n) sum++,cnt=now.dx;
        if(now.x==n&&sum&&now.dx!=cnt) return now.dx;

        for(int i=head[now.x];i;i=nt[i])
        {
            int y=ver[i],z=edge[i];
            q.push(node(y,now.dx+z,d[y]));
        }
    }
    return -1;
}

int main(void)
{
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        memset(head,0,sizeof(head));
        tot=1;
        int x,y,z;
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d%d",&x,&y,&z);
            add(x,y,z);
            add(y,x,z);
        }
        Dij();
        printf("%d\n",s2());

    }


    return 0;
}

三、两次Dijkstra：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<map>
#include<queue>
#include<set>
#define ll long long
#define llu unsigned ll
using namespace std;
const int mod=1000000007;
const int maxn=200100;
const int maxx=5200;
const int inf=0x3f3f3f3f;
int head[maxx],edge[maxn],ver[maxn],nt[maxn];
int d1[maxx],d2[maxx];
bool ha[maxx];
int tot=1,n,m;


void add(int x,int y,int z)
{
    ver[++tot]=y,edge[tot]=z;
    nt[tot]=head[x],head[x]=tot;
}



void Dij(int s,int *d)
{
    memset(ha,0,sizeof(ha));
    d[s]=0;
    priority_queue<pair<int,int> >q;
    q.push(make_pair(0,s));

    while(q.size())
    {
        int x=q.top().second;
        q.pop();
        if(ha[x]) continue;
        ha[x]=true;

        for(int i=head[x];i;i=nt[i])
        {
            int y=ver[i],z=edge[i];
            if(d[y]>d[x]+z)
            {
                d[y]=d[x]+z;
                q.push(make_pair(-d[y],y));
            }
        }
    }
    return ;
}


int main(void)
{
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        memset(head,0,sizeof(head));
        tot=1;
        memset(d1,0x3f,sizeof(d1));
        memset(d2,0x3f,sizeof(d2));
        int x,y,z;
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d%d",&x,&y,&z);
            add(x,y,z);
            add(y,x,z);
        }
        Dij(1,d1);
        Dij(n,d2);
        int ans=0x3f3f3f3f;
        for(int i=2;i<=tot;i++)
        {
            int xx=ver[i],yy=ver[i^1],zz=edge[i];
            int cc=d1[xx]+d2[yy]+zz;
            if(cc!=d1[n]) ans=min(ans,cc);
        }
        printf("%d\n",ans);

    }


    return 0;
}