学步园

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<queue>
using namespace std;
#define manx 1009
const int inf=99999999;
int g[manx][manx],pre[manx];
int n,m,dist[manx],sum;
int g1[manx][manx];
bool vist[manx];

void dijkstra(){
    for(int i=1;i<=n;i++){
        dist[i]=g[1][i];
        vist[i]=0;
        pre[i]=1;
    }
    vist[1]=1; dist[1]=0;
    for(int i=1;i<=n;i++){
        int max = inf, k = -1;
        for(int j=1;j<=n;j++){
            if(!vist[j] && dist[j]<max)
                max = dist[j], k = j;
        } 
        if(k == -1) break;
        vist[k] = 1;
        for(int j=1;j<=n;j++){
            if(!vist[j] && dist[j]>dist[k]+g[k][j]){
                dist[j] = dist[k]+g[k][j];
                pre[j] = k;
            }       
        }
    }
}

void init(int n){
    for(int i=0;i<=n;i++)
        for(int j=0;j<=n;j++){
            g[i][j] = g1[i][j] = inf;
        }    
}

void spfa(){
    queue<int>que;
    for(int i=1;i<=n;i++){
        dist[i] = inf;
        vist[i] = 0;
    }
    int v = 1;
    vist[v] = 1;
    dist[v] = 0;
    que.push(v);
    while(!que.empty()){
        int u = que.front();
        que.pop();
        vist[u] = 0;
        for(int i=1;i<=n;i++){
            if(dist[i]>dist[u]+g[u][i]){
                dist[i] = dist[u] + g[u][i];
                if(!vist[i]){
                	vist[i] = 1;
                	que.push(i);
                }    
            }       
        }
    }
}

int main(){
    int t;
    scanf("%d",&t);
    while(t--){
    	scanf("%d%d",&n,&m);
        int a,b,c;
        init(n);
        for(int i=0;i<m;i++){
            scanf("%d%d%d",&a,&b,&c);
            if(g[a][b]>c){ 
                g1[a][b]=g1[b][a]=g[a][b];
                g[a][b]=g[b][a]=c;
            }    
            else if(g1[a][b]>c)
            	g1[a][b]=g1[b][a]=c;
        }
        dijkstra();
        int ans = dist[n];
        int x = n;
        while(pre[x]!=x){
            int val = g[x][pre[x]];
            g[x][pre[x]] = g[pre[x]][x] = g1[pre[x]][x];
            spfa();
            if(ans>=inf) break;
            ans = ans > dist[n] ? ans : dist[n];
            g[x][pre[x]] = g[pre[x]][x] = val;
            x = pre[x];
        }
        if(ans>=inf) printf("-1\n");
        else  printf("%d\n",ans);
    }
}