分析

本题主要就是一个转化
当我们看到数据范围，就可以大胆猜测较高复杂度的算法
因为维护最大值比较麻烦
我们考虑用二分答案限制最大值
然后就可以顺理成章的想出
将的路径长度标为1
跑一个最短路
如果最后的Dist[T]那么这就是一个可行的解
以此二分即可求得答案

代码

//P1948
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <cmath>

#define LL long long
#define Cl(X,Y) memset((X),(Y),sizeof(X))
#define FOR(i,A,B) for(int i=A;i<=B;i++)
#define BOR(i,A,B) for(int i=A;i>=B;i--)
#define INF 0x3f3f3f3f
using namespace std;
const int MaxN=2e4+10;

int Next[MaxN<<1],Head[MaxN],End[MaxN<<1],Cur,Val[MaxN<<1];
int Total,Side,Limit,cnt,h[1005],Dist[1005],Mine[1005];
bool Jud[1005];

inline void Add_Edge(int u,int v,int w) {
    Next[++Cur]=Head[u];
    Head[u]=Cur;
    End[Cur]=v;
    Val[Cur]=w;
}

inline bool check(int x) {
    Cl(Dist,0x3f);
    int R=0,L=1,i,New,s;
    Dist[1]=0;
    Mine[R]=1;
    Jud[1]=1;
    while(R!=L) {
        New=Mine[R];R++;
        if(R==1001)R=0;
        i=h[New];
        for(int i=Head[New];i;i=Next[i]) {
            if(Val[i]>x) s=Dist[New]+1;
            else s=Dist[New];
            if(s<Dist[End[i]]) {
                Dist[End[i]]=s;
                if(!Jud[End[i]]) {
                    Mine[L++]=End[i];
                    Jud[End[i]]=1;
                    if(L==1001)L=0;
                }
            }
        }
        Jud[New]=0; 
    }
    if(Dist[Total]<=Limit)return 1;
    return 0;
 }
int main() {
    scanf("%d %d %d",&Total,&Side,&Limit);
    int u,v,L,l=0,r=1000000,mid;
    FOR(i,1,Side) {
        scanf("%d %d %d",&u,&v,&L);
        Add_Edge(u,v,L);
        Add_Edge(v,u,L);
    }
    int Ans=-1;
    while(l<=r) {
        mid=(l+r)>>1;
        if(check(mid)){r=mid-1;Ans=mid;}
        else l=mid+1;
    }
    printf("%d\n",Ans);
    system("pause");
    return 0;
}