# Shortest Route CodeChef Solution | SHROUTE

Hello coders, today we are going to solve Shortest Route CodeChef Solution in C++, Java and Python.

There are N cities in Chefland numbered from 1 to N and every city has a railway station. Some cities have a train and each city has at most one train originating from it. The trains are represented by an array A, where Ai=0 means the i-th city doesn’t have any train originating from it, Ai=1 means the train originating from the i-th city is moving right (to a higher numbered city), and Ai=2 means the train originating from the i-th city is moving left (to a lower numbered city).

Each train keeps on going forever in its direction and takes 1 minute to travel from the current station to the next one. There is a special station at city 1 which lets travellers instantaneously teleport to any other station that currently has a train. Teleportation and getting on a train once in the city both take 0 minutes and all trains start at time 0.

There are M travellers at city 1, and the i-th traveller has destination city Bi. They ask Chef to guide them to teleport to a particular station from which they can catch a train to go to their destination in the least time possible. In case it’s not possible for a person to reach his destination, print −1.

Note: The input and output of this problem are large, so prefer using fast input/output methods.

## Input Format

• The first line contains an integer T, the number of test cases. Then the test cases follow.
• Each test case contains three lines of input.
• The first line contains two integers N, M.
• The second line contains N integers A1,A2,…,AN.
• The third line contains M integers B1,B2,…,BM.

## Output Format

For each test case, output M space-separated integers C1,C2,…,CM, where Ci is the minimum time required by the i-th traveller to reach his destination and if the i-th traveller can’t reach his destination, Ci=−1.

## Constraints

• 1≤N,M≤105
• 0≤Ai≤2
• 1≤Bi≤N
• The sum of N over all test cases is at most 106.
• The sum of M over all test cases is at most 106.

Subtask #1 (100 points): original constraints

Sample Input

``````3
5 1
1 0 0 0 0
5
5 1
1 0 0 0 2
4
5 2
2 0 0 0 1
3 1``````

Sample Output

``````4
1
-1 0``````

## Explanation

Test Case 1: The only person takes the train from station 1 and hence takes |5−1|=4 minutes to reach his destination.

Test Case 2: The only person takes the train from station 5 and hence takes |5−4|=1 minute to reach his destination.

Test Case 3: Since no train passes station 3, it’s impossible for the first person to reach his destination and since the second person is already at station 1, it takes him 0 minutes to reach his destination.

## Solution – Shortest Route CodeChef Solution

### C++

```#include <bits/stdc++.h>

using namespace std;
#define int long long
#define MOD 1000000007

void solve(){
int i;
int n,m; cin>>n>>m;
int a[n];
int b[m];

for (i=0;i<n;i++) {
cin>>a[i];}
for(i=0;i<m;i++){
cin>>b[i];}

int max=1e9;
map<int,int>mp;

for(i=0;i<n;i++)  {
if(i==0) mp[i]=0;
else if (a[i]!=0) mp[i]=0;

else mp[i]=max;

}

int right=-1;
for(i=0;i<n;i++) {
if(a[i]==1) right=i;
if(right!=-1) {
if(a[i]==0)
mp[i]=min(mp[i],i-right);
}
}

int left =-1;
for(i=n-1;i>=0;i--) {
if(a[i]==2) left=i;
if(left!=-1) {
if(a[i]==0)
mp[i] =min(mp[i],left-i);

}
}

for(i=0;i<m;i++){
int j=b[i]-1;
if(mp[j]!=max)
cout<<mp[j]<<" ";
else
cout<< -1<<" ";
}

cout<<"\n";
}

int32_t main(){
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

int t;
cin>>t;
// t = 1;
int _=1;
while(t--){
// cout<<"Case #"<<_++<<": ";
solve();
}
return 0;
}

```

Disclaimer: The above Problem (Shortest Route) is generated by CodeChef but the Solution is Provided by CodingBroz. This tutorial is only for Educational and Learning Purpose.