#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<memory.h>
using namespace std;
const int INF=1000000000;
const int N=10005;
struct Edge{int v,c,nt;};
Edge e[20*N];
int nt[N],len,n,m;
void insert(int a,int b,int c)
{
    e[len].v=b;
    e[len].c=c;
    e[len].nt=nt[a];
    nt[a]=len++;
}
int path[N],dis[N],vis[N];
struct Q{
    int v,c;
    friend bool operator<(Q a,Q b)
    {return a.c>b.c;}
};
int dijkstra(int st,int ed)
{
    for(int j=1;j<=n;j++)dis[j]=INF,vis[j]=1;
    priority_queue<Q> q;
    Q s;s.v=1;s.c=0;q.push(s);
    path[st]=dis[st]=0;
    while(!q.empty()){
        Q t=q.top();q.pop();
        if(!vis[t.v])continue;
        vis[t.v]=0;
        for(int i=nt[t.v];i;i=e[i].nt){
            int u=e[i].v;
            if(dis[u]>t.c+e[i].c)
            {
                Q in;
                in.v=u;
                dis[u]=in.c=t.c+e[i].c;
                path[u]=t.v;
                q.push(in);
            }
        }
    }
    return dis[ed];
}
void change()
{
    int i,j,jj,u;
    for(i=n;i>1;i=u){
        u=path[i];
        for(j=nt[u],jj=0;j;jj=j,j=e[j].nt)
            if(e[j].v==i&&e[j].c==dis[i]-dis[u])break;
        if(j==nt[u])nt[u]=e[j].nt;
        else e[jj].nt=e[j].nt;
        insert(i,u,-e[j].c);
    }
    for(i=1;i<=n;i++)
        for(j=nt[i];j;j=e[j].nt)
            e[j].c+=dis[i]-dis[e[j].v];
}
int main(){
    int i,j,k;
    while(cin>>n>>m)
    {
        len=1;
        for(i=0;i<m;i++)
        {
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            insert(a,b,c);
            insert(b,a,c);
        }
        int ans=0;
        ans+=dijkstra(1,n);
        change();
        ans=dijkstra(1,n)+ans*2;
        printf("%d\n",ans);
    }
	return 0;
}

• Re:两次dijkstra最短路过的，原理和网络流一样，有重边！ (5) abcdefgzzzz 2016-02-27 19:27:06