[HOJ] 59 - 次短路

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
#define N 5005
#define INF 999999999
struct P{
    int v,c;
    friend bool operator < (P a,P b){
        return a.c>b.c;
    }
};
struct T{
    int a,b;
}pre[N]={0};
int is[N]={0},d[N],now=-1,n,m;
vector<T> arr;
vector<P> s[N];
priority_queue<P> heap;
void init(){
    int i;
    memset(is,0,sizeof(is));
    for(i=1;i<=n;i++)
        d[i]=INF;
}
void dijkstra(int S){
    int i;
    d[S]=0;
    heap.push((P){S,0});
    while(heap.size()){
        P out=heap.top();
        heap.pop();
        int u=out.v;
        if(is[u]==1) continue;
        is[u]=1;
        for(i=0;i<s[u].size();i++){
            P in=s[u][i];
            if(now!=-1 && arr[now].a==u && arr[now].b==i) continue;
            if(d[u]+in.c<d[in.v]){
                d[in.v]=d[u]+in.c;
                pre[in.v]=(T){u,i};
                heap.push((P){in.v,d[in.v]});
            }
        }
    }
}
int main(){
    int x,y,z,i,j,ans=INF,tmp;
    scanf("%d%d",&n,&m);
    for(i=0;i<m;i++){
        scanf("%d%d%d",&x,&y,&z);
        s[x].push_back((P){y,z});
        s[y].push_back((P){x,z});
    }
    init();
    dijkstra(1);
    int u=n;
    while(pre[u].a){
        arr.push_back(pre[u]);
        u=pre[u].a;
    }
    tmp=d[n];
    arr.push_back((T){n,0});
    for(j=0;j<arr.size();j++){
        init();
        dijkstra(arr[j].a);
        for(i=1;i<=n;i++){
            if(i!=arr[j].a && d[i]!=INF && tmp+d[i]*2<ans)
                ans=tmp+d[i]*2;
        }
    }

    for(now=0;now<arr.size()-1;now++){
        init();
        dijkstra(1);
        if(d[n]<ans) ans=d[n];
    }
    if(ans!=INF) printf("%d\n",ans);
    else puts("0");
}