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

**Task**

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.

**Subtasks**

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