思路：
用步数做距离，索敌值作为判断标准bfs
#include <iostream> #include <stack> #include <cstdio> #include <cstring> #include <set> #include <queue> #include <vector> using namespace std; const int maxn=10050; int n,m,k,t; vector <pair<int,int> >vec[maxn]; int dis[maxn]; bool bfs(int val) { const int inf=0x3f3f3f3f; for(int i=1;i<=n;i++) dis[i]=inf; queue<int>q; q.push(1); dis[1]=0; while(!q.empty()) { int u=q.front(); if(dis[u]>k) return false; if(u==t) return true; q.pop(); for(int i=0;i<vec[u].size();i++) { int v=vec[u][i].first; int w=vec[u][i].second; if(w<=val&&dis[v]>dis[u]+1) { dis[v]=dis[u]+1; q.push(v); } } } return false; } bool judge(int k) { if(bfs(k)) { return true; } return false; } int main() { scanf("%d%d%d%d",&n,&m,&k,&t); for(int i=1;i<=m;i++) { int u,v,w; scanf("%d%d%d",&u,&v,&w); vec[u].push_back(make_pair(v,w)); vec[v].push_back(make_pair(u,w)); } int l=1,r=10000000; int ans=100000000; while(l<=r) { int mid=(l+r)/2; if(judge(mid)) { ans=mid; r=mid-1; } else { l=mid+1; } } printf("%d\n",ans); }
