pre数组用来存路径

然后先预处理最短路

再枚举删掉最短路上的每条边再dijkstra，求每次1->n的最大值

可是即使这样还是TLE...

PS :有快读

请各位帮忙看看吧，谢谢！

#include<bits/stdc++.h>
#define For(i,m,n) for(register int i=m;i<n;i++)
using namespace std;
template <class T>
inline void read(T &x)
{
	x=0;T f=1;char ch=getchar();
	while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
	while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
	x=x*f;
}
const int MaxN = 2e3, MaxM = 5000100;
const int INF=1e8;
struct edge{
    int next;
    int to;
    int dis;
    int from;
}e[MaxM];
int head[MaxN],pre[MaxN],tot;
int resDis[MaxN];
bool vis[MaxN];
struct node{
    int dis;
    int x;
};
struct cmp{
    bool operator()(node& n1,node &n2){
        return n1.dis>n2.dis;
    }
};
inline void addEdge(int u,int v,int w)
{
    tot++;
    e[tot].from=u;
    e[tot].to=v;
    e[tot].dis=w;
    e[tot].next=head[u];
    head[u]=tot;
}
int n,m;
priority_queue<node,vector<node>,cmp > Q;
inline void dijkstra(int s,int dele_u,int dele_v)
{
    For(i,1,n+1)    resDis[i]=INF,vis[i]=0;
    resDis[s]=0;
    Q.push((node){0,s});
    while(Q.size()){
        node nowState=Q.top();Q.pop();
        int nowU=nowState.x;
        if(vis[nowU])    continue;
        vis[nowU]=1;
        for(int i=head[nowU];i;i=e[i].next){
            int v=e[i].to;
            if(dele_u==nowU&&dele_v==v)  continue;
            if(resDis[v]>resDis[nowU]+e[i].dis){
                resDis[v]=resDis[nowU]+e[i].dis;
                pre[v]=nowU;                
            }
            if(!vis[v]){
                Q.push((node){resDis[v],v});
            }
        }
    }
}

void input()
{
    read(n);read(m);
    For(i,1,m+1){
        int u,v,w;
        read(u),read(v),read(w);
        addEdge(u,v,w);
        addEdge(v,u,w);
    }
}

int main()
{
    // freopen("out.txt","w",stdout);
    input();
    dijkstra(1,0,0);
    int now_u=pre[n];
    int now_v=n;
    vector<pair<int,int> > path;
    while(now_u){
        path.push_back(make_pair(now_u,now_v));
        now_v=now_u;
        now_u=pre[now_v];
    }
    int maxx=0;
    For(i,0,path.size()){
        pair<int,int> &tmp=path[i];
        dijkstra(1,tmp.first,tmp.second);
        maxx=max(maxx,resDis[n]);
    }
    cout<<maxx;
    return 0;
}