1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int i,j,m,n,p,k,t,cnt,vis[100005],dis[100005],fox[100005],Q[100005],x,y,z;
int l,r,mid,k1;
struct Node{int ed,before,cost;}s[300005];
void add(int x,int y,int z)
{ 
  s[++k1].ed=y; s[k1].before=fox[x]; fox[x]=k1; s[k1].cost=z;
}
int check(int x)
{
      cnt++;
      dis[1]=0;
      Q[Q[0]=1]=1;
      vis[1]=cnt;
      for (i=1;i<=Q[0];i++)
      {
          p=Q[i];
          for (j=fox[p];j;j=s[j].before)
          if (s[j].cost<=x&&vis[s[j].ed]!=cnt)
          { 
               vis[s[j].ed]=cnt;
               Q[++Q[0]]=s[j].ed;
               dis[s[j].ed]=dis[p]+1;
              if (s[j].ed==t) return dis[t];
        }
}
return k+1;
}
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX