Untitled
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...