#include<stdio.h>
#include<string.h>
#define N 5008
#define INF 0xffff;
int lowcast[N];
int num[N];
unsigned short w[N][N];
int ans;
int n,m;
void input();
struct node {
    int u;
    int v;
    int value;
};
node eg[200005];
void dikjstra(int start);
int getsecond();
void show();
int main(){
    //freopen("1.txt","r",stdin);
    while (scanf("%d%d",&n,&m)!=EOF){
        input();
        ans=0;
        dikjstra(1);
        for (int i=1;i<=n;i++){
            num[i]=lowcast[i];
        }
        dikjstra(n);
        ans=getsecond();
        //show();
        printf("%d\n",ans);
    }
}
void input(){
    int a;int b;int c;
    int s=1;
    for (int i=1;i<N;i++){
        for (int j=1;j<N;j++)
            if (i==j)
                w[i][j]=0;
            else
            w[i][j]=INF;
    }
    for (int i=0;i<m;i++){
        scanf("%d%d%d",&a,&b,&c);
        eg[i+1].u=a;
        eg[i+1].v=b;
        eg[i+1].value=c;
        if (c<w[a][b]){
            w[a][b]=w[b][a]=c;
        }
    }
}
void dikjstra(int start){
    memset(lowcast,0,sizeof(lowcast));
    int used[N]={0};
    int i,j,k;
    for (i=1;i<=n;i++){
        lowcast[i]=w[start][i];
    }
    lowcast[start]=0;
    used[start]=1;
    for (i=0;i<n;i++){
        int min=INF;
        j=1;
        for (k=1;k<=n;k++){
            if (min>lowcast[k]&&!used[k]){
                min=lowcast[k];
                j=k;
            }
        }
        used[j]=1;
        for (k=1;k<=n;k++){
            if (lowcast[j]+w[j][k]<lowcast[k]&&!used[k]){
                lowcast[k]=lowcast[j]+w[j][k];
            }
        }
    }
}
int getsecond(){
    int i,j,k;
    int min=INF;
    int t;
    for (i=1;i<=m;i++){
        int tempu=eg[i].u;
        int tempv=eg[i].v;
        int tempvalue=eg[i].value;
        t=lowcast[tempv]+num[tempu]+tempvalue;
        if (t<min&&t>lowcast[1]){
            min=t;
        }
        t=lowcast[tempu]+num[tempv]+tempvalue;
        if (t<min&&t>lowcast[1]){
            min=t;
        }
    }
    return min;
}
void show(){
    for (int i=1;i<=n;i++){
        for (int j=1;j<=n;j++){
            printf("%d ",w[i][j]);
        }
        printf("\n");
    }
    for (int i=1;i<=n;i++){
        printf("%d ",lowcast[i]);
    }
    printf("\n");
    for (int i=1;i<=n;i++){
        printf("%d ",num[i]);
    }
    printf("\n");
}

• 可以用SPFA啊。 (2669) yygy 2014-07-24 16:54:37