This post is written in Chinese. Please consider using Google Translate

方法为二分答案。

我们暂且不考虑最优解的问题，假设A为一个可行解。可以知道如果A成立，则B(B>=A)一定成立。这说明解具有单调性，即所有可行解是一个单调序列。我们模仿二分查找的方法，对答案进行二分尝试，对最优解逐步逼近。

对于这道题，假设A=4这个解成立，则说明顶点1到N之间必存在某路径，满足这条路径中长度大于4的边不超过K条（如果超过K条，4就不是去除K条以外的最大值了，与题意矛盾）。

1. 判断给定的A是否为可行解，即求从顶点1到顶点N的某条路径上，长度大于A的边最少有多少条。如果最少的条数小于等于K，则A为一个可行解。
2. 对于求最少的条数，可以在原图的基础上构造一个新图，改变边权。如果一条边原来的权值大于A，则在新图中将其权值设为1；如果一条边原来的权值小于等于A，则在新图中将其权值设为0。
3. 然后求出从顶点1到N的最短路径长度D，D即为从顶点1到顶点N的某条路径上，长度大于A的边最少有多少条。
4. 如果D<=K，则A为可行解。

/*
ID: cmykrgb1
PROG: phoneline
LANG: C++
*/

#include <iostream>
#define MAX 1001
#define MAXP 10001
#define MAXL 1000000
using namespace std;

class tQueue
{
public:
    class linklist
    {
    public:
        linklist* next;
        int value;
        linklist()
        {
            next=0;
            value=0;
        }
    };
    linklist *first,*last;
    int size;
    bool inq[MAX];
    void add(int p)
    {
        if (size==0)
            first=last=new linklist;
        else
            last=last->next=new linklist;
        last->value=p;
        inq[p]=true;
        size++;
    }
    int del()
    {
        int rtn=first->value;
        inq[rtn]=false;
        linklist *tfirst=first;
        first=first->next;
        delete tfirst;
        size--;
        return rtn;
    }
    void reset()
    {
        size=0;
        first=last=0;
        memset(inq,0,sizeof(inq));
    }
    tQueue()
    {
        reset();
    }
};

class list
{
public:
    list *next;
    int p;
    list(int &tp)
    {
        p=tp;
        next=0;
    }
};

class tadjl
{
public:
    list *first,*last;
    tadjl()
    {
        first=last=0;
    }
    void ins(int p)
    {
        if (first)
            last=last->next=new list(p);
        else
            first=last=new list(p);
    }
};

tadjl adjl[MAX];
tQueue Q;
int dis[MAX][MAX],sp[MAX];
int N,P,K;

void init()
{
    int i,a,b,v;
    freopen("phoneline.in","r",stdin);
    freopen("phoneline.out","w",stdout);
    cin >> N >> P >> K;
    for (i=1;i<=P;i++)
    {
        scanf("%d%d%d",&a,&b,&v);
        adjl[a].ins(b);
        adjl[b].ins(a);
        dis[a][b]=dis[b][a]=v;
    }
}

bool check(int A)
{
    list *k;
    int i,j,v;
    Q.reset();
    Q.add(1);
    memset(sp,0xf,sizeof(sp));
    sp[1]=0;
    while (Q.size)
    {
        i=Q.del();
        for (k=adjl[i].first;k;k=k->next)
        {
            j=k->p;
            v=dis[i][j];
            if (v>A)
                v=1;
            else
                v=0;
            if (sp[i]+v<sp[j])
            {
                sp[j]=sp[i]+v;
                if (!Q.inq[j])
                    Q.add(j);
            }
        }
    }
    return sp[N]<=K;
}

void solve()
{
    int a,b,m;
    a=0;
    b=MAXL;
    while (a<b)
    {
        m=(a+b)/2;
        if (check(m))
            b=m;
        else
            a=m+1;
    }
    if (a==MAXL)
        a=-1;
    cout << a << endl;
}

int main()
{
    init();
    solve();
    return 0;
}