Untitled

 avatar
unknown
plain_text
4 years ago
1.7 kB
6
Indexable
#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define pb push_back
int main()
{     
      int t;
      cin>>t;
      while(t--){
            int n,m,i,j,a,b,l,r,mid,ans=-1,ok,s,f,d;
            cin>>n>>m;
            int from[m+2],to[m+2],temp[m+2];
            vector<pair<int,int> >v[n+3];
            for(i=0;i<m;i++){cin>>from[i];}
            for(i=0;i<m;i++){cin>>to[i];}
            for(i=0;i<m;i++){cin>>temp[i];}
            for(i=0;i<m;i++){
                  v[from[i]].pb({to[i],temp[i]});
            }     
            cin>>s>>f>>d;
            l=0;r=1e3;
            while(l<=r){
                  ok=0;
                  mid=(l+r)/2;
                  queue<pair<int,int> >q;
                  q.push({s,d});
                  while(q.size()>0){
                        pair<int,int>p=q.front();
                        q.pop();
                        a=p.f;      b=p.s;
                        if(b==0){
                              if(a==f){
                                    ans=mid;
                                    ok=1;
                                    while(q.size()>0){q.pop();}
                                    break;
                              }
                              continue;
                        }
                        for(i=0;i<v[a].size();i++){
                              if(v[a][i].s<=mid){
                                    q.push({v[a][i].f,b-1});
                              }
                        }
                  }
                  if(ok==1){
                        r=mid-1;
                  }
                  else{l=mid+1;}
            }
            cout<<ans<<"\n";
      }
}
Editor is loading...