解题思路
这道题有两种方法可以做，第一种可以选择dp，与BZOJ 2763 飞行路线的做法相似。定义dp[x][i] 表示到了x这个点，用了i次免费的最小值，之后便可以在最短路中转移。我用的是spfa，时间复杂度O(NMt) t是一个常数，还是可以过得。
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
using namespace std;
const int MAXN = 1005;
const int MAXM = 10005;
const int inf = 0x3f3f3f3f;
inline int rd(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)) {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return x*f;
}
int n,m,k;
int head[MAXN],cnt;
int to[MAXM<<1],nxt[MAXM<<1],val[MAXM<<1];
int dp[MAXN][MAXN],ans=inf;
queue<int> q;
bool vis[MAXN];
inline void add(int bg,int ed,int v){
to[++cnt]=ed,val[cnt]=v,nxt[cnt]=head[bg],head[bg]=cnt;
}
inline void spfa(){
vis[1]=1;dp[1][0]=0;q.push(1);
while(q.size()){
int x=q.front();q.pop();
vis[x]=0;
for(register int i=head[x];i;i=nxt[i]){
int u=to[i];
if(dp[u][0]>max(dp[x][0],val[i])){
dp[u][0]=max(dp[x][0],val[i]);
if(!vis[u]){
q.push(u);
vis[u]=1;
}
}
for(register int j=1;j<=k;j++){
if(dp[u][j]>min(dp[x][j-1],max(dp[x][j],val[i]))){
dp[u][j]=min(dp[x][j-1],max(dp[x][j],val[i]));
if(!vis[u]){
vis[u]=1;
q.push(u);
}
}
}
}
}
}
int main(){
memset(dp,0x3f,sizeof(dp));
n=rd();m=rd();k=rd();
for(register int i=1;i<=m;i++){
int x=rd(),y=rd(),z=rd();
add(x,y,z);add(y,x,z);
}spfa();
for(register int i=0;i<=k;i++)
ans=min(ans,dp[n][i]);
if(ans==inf) puts("-1");
else printf("%d",ans);
return 0;
}第二种做法是用二分答案，二分一个花费，之后把原图里花费比二分出的多的看做边权为1的边，少的看做边权为0的边，之后用一个双端队列bfs可以算出最短路。双端队列bfs的做法是如果这条边为1，就把要更新的点放到队尾，否则放在队首，时间复杂度O((N+M)log MAX_L)，跑的更快一些
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<deque>
using namespace std;
const int MAXN = 1005;
const int MAXM = 10005;
inline int rd(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)) {x=(x<<1)+(x<<3)+ch-48;ch=getchar();}
return x*f;
}
int n,m,k,ans;
int head[MAXN],cnt;
int nxt[MAXM<<1],to[MAXM<<1],val[MAXM<<1];
int mx,dis[MAXN];
bool vis[MAXN];
deque<int> q;
inline void add(int bg,int ed,int v){
nxt[++cnt]=head[bg],head[bg]=cnt,val[cnt]=v,to[cnt]=ed;
}
inline bool check(int len){
memset(vis,false,sizeof(vis));
memset(dis,0x3f,sizeof(dis));
q.push_back(1);vis[1]=1;dis[1]=0;
while(q.size()){
int x=q.front();q.pop_front();
for(register int i=head[x];i;i=nxt[i]){
int u=to[i];
if(val[i]<=len){
dis[u]=min(dis[u],dis[x]);
if(!vis[u]) q.push_front(u);
}
else if(val[i]>len){
dis[u]=min(dis[u],dis[x]+1);
if(!vis[u]) q.push_back(u);
}
vis[u]=1;
}
}
if(dis[n]<=k) return true;
return false;
}
int main(){
n=rd();m=rd();k=rd();
for(register int i=1;i<=m;i++){
int x=rd(),y=rd(),z=rd();
add(x,y,z);add(y,x,z);
mx=max(z,mx);
}
int l=0,r=mx;
while(l<=r){
int mid=l+r>>1;
if(check(mid)) ans=mid,r=mid-1;
else l=mid+1;
}
if(!ans && !check(0)) puts("-1");
else printf("%d",ans);
return 0;
}