思路

二分答案的做法很容易理解，这里就不多赘述了。主要谈谈我对第一种解法的理解。

首先拿到题目，熟悉dp的同学很快就想到了：令f[x, p]为从1走到x，花了p次机会的答案。最终所求为min{f[n, t]},t∈[0,k]

设计完状态就想转移方程，这也不难。考虑一条边(x,y,z)对dp的贡献：

若在这条边不使用机会：f[y, p] = min(f[y, p], max(f[x, p], z))

若在这条边使用机会：f[y, p+1] = min(f[y, p+1], f[x, p])

接下来直接dp就行了。但是码代码时不知道如何dp，也就是不知道dp顺序。

回过头来看题，发现图并没有说是DAG。那么转移就有后效性了。那么借助spfa的思想——迭代思想性。

spfa核心算法思想即不断松弛，直到松弛不了结束。

那我不知道dp顺序，我就一直dp，dp到无法继续dp为止（也就是dp无法更新状态为止）

这两者是不是很像呢？于是我们将以前spfa中的松弛条件替换为dp转移方程就ok了。

这样就无需考虑dp顺序了，完成。

最后，我写的代码跟其它题解不太一样，更简单些。

我的spfa队列里开的是一个pair，即f[x, p]中的x和p，这样就可以大大减小编程难度，而且直接把原松弛条件换成dp转移即可。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;

const int N=1005;
const int M=20005;
const int K=1005;

struct E {int nex,to,dis;} e[M];
int n,m,k,num,ans=0x3f3f3f3f;
int h[N];
int dis[N][K];
bool vis[N][K];

void add(int u,int v,int w) {e[++num]={h[u],v,w},h[u]=num;}

void spfa() {
    queue<pair<int,int>> que;
    que.push(make_pair(1,0)),dis[1][0]=0;
    while(que.size()) {
        int x=que.front().first,p=que.front().second;
        vis[x][p]=0,que.pop();
        for(int i=h[x];i;i=e[i].nex) {
            int y=e[i].to;
            if(max(dis[x][p],e[i].dis)<dis[y][p]) {
                dis[y][p]=max(dis[x][p],e[i].dis);
                if(!vis[y][p]) {
                    que.push(make_pair(y,p));
                    vis[y][p]=1;
                }
            }
            if(p+1<=k && dis[x][p]<dis[y][p+1]) {
                dis[y][p+1]=dis[x][p];
                if(!vis[y][p+1]) {
                    que.push(make_pair(y,p+1));
                    vis[y][p+1]=1;
                }
            }
        }
    }
}

int main()
{
    cin>>n>>m>>k;
    for(int i=1;i<=m;i++) {
        int u,v,w; scanf("%d%d%d",&u,&v,&w);
        add(u,v,w),add(v,u,w);
    }
    memset(dis,0x3f,sizeof(dis));
    spfa();
    for(int i=0;i<=k;i++) ans=min(ans,dis[n][i]);
    if(ans==0x3f3f3f3f) ans=-1;
    cout<<ans;
    return 0;
}