感觉和 [NOI2018] 归程 有点像（？
考虑对每个询问二分答案，设二分到的答案是 \(x\)，要判断路径上的 \(k\) 大值是否能不大于 \(x\)，只需先将价值不大于 \(x\) 的所有边的边权设为 \(0\)，其他边设为 \(1\)，跑一遍 \(a\) 到 \(b\) 的最短路，看最短路长度是否不大于 \(k\) 即可。因为 \(x\) 的排名只和价值比它大的边的数量有关系，比它小的边可以随便走。
现在我们只需预处理出任意时刻任意两点间的最短路即可。将所有边按边权从小到大加入，显然如果一条边连接的两点已经被边权为 \(0\) 的边联通了，这条边加入就没什么意义了。每加入一条边就用类似 Floyd 的方法松弛一遍。总时间复杂度 \(O(n^3 + q\log n)\)。
#include<bits/stdc++.h>
inline void rd(){}
template<typename T,typename ...U>
inline void rd(T &x,U &...args){
int ch=getchar();
T f=1;x=0;
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
x*=f;rd(args...);
}
const int N=3e5+5,D=405,INF=1e9+7;
int T,n,m,q;
int dis[D][D][D],cnt,w[D];
struct node{int x,y,z;}e[N];
inline void Solve(){
rd(n,m,q);cnt=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)dis[0][i][j]=INF;
for(int i=1;i<=n;i++)dis[0][i][i]=0;
for(int i=1;i<=m;i++){
rd(e[i].x,e[i].y,e[i].z);
dis[0][e[i].x][e[i].y]=dis[0][e[i].y][e[i].x]=1;
}
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
dis[0][i][j]=std::min(dis[0][i][k]+dis[0][k][j],dis[0][i][j]);
}
}
}
std::sort(e+1,e+m+1,[](node a,node b){return a.z<b.z;});
for(int i=1;i<=m;i++){
if(dis[cnt][e[i].x][e[i].y]==0)continue;
++cnt;w[cnt]=e[i].z;
for(int j=1;j<=n;j++)
for(int k=1;k<=n;k++)dis[cnt][j][k]=dis[cnt-1][j][k];
dis[cnt][e[i].x][e[i].y]=0;
for(int j=1;j<=n;j++){
for(int k=1;k<=n;k++){
dis[cnt][j][k]=std::min(dis[cnt][j][k],dis[cnt][j][e[i].x]+dis[cnt][e[i].y][k]);
dis[cnt][j][k]=std::min(dis[cnt][j][k],dis[cnt][j][e[i].y]+dis[cnt][e[i].x][k]);
}
}
}
while(q--){
int a,b,k;rd(a,b,k);
int L=1,R=cnt;
while(L<=R){
int mid=(L+R)>>1;
if(dis[mid][a][b]<=k-1)R=mid-1;
else L=mid+1;
}
printf("%d\n",w[L]);
}
}
signed main(){
rd(T);
while(T--)Solve();
return 0;
}