HackerEarth Mancunian Goes To The Derby problem solution

In this HackerEarth Mancunian Goes To The Derby problem solution It's derby weekend in Manchester. United vs City. The Red Devils vs The Noisy Neighbours. Mancunian has been waiting for this for a long time. But due to the huge popularity of the match, there is a lot of traffic on the streets. To control the rush, the police have devised an ingenious system of one-way roads which ensures smooth flow of traffic.

The city of Manchester can be modeled as a graph of N nodes and E edges. Vertices are numbered from 1 to N. Each edge is a one-way road but direction depends on the time at which roads are traversed. If there is a road between checkpoints A and B, it is directed from A to B in even-numbered seconds and B to A in odd-numbered seconds. Mancunian can move between adjacent vertices taking time 1 second. He can always choose to wait at some checkpoint for the roads to change their orientation. Mancunian's house is located at the point numbered 1 and the venue of the match, Old Trafford (the Theatre of Dreams) is located at point N.

Given Q possible start times, for each query you have to find out whether Mancunian can reach the stadium before the start of the match. He always starts his journey at time 0.

HackerEarth Mancunian Goes To The Derby problem solution.

#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define MOD (1000000007LL)
#define LEFT(n) (2*(n))
#define RIGHT(n) (2*(n)+1)
 
using namespace std;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;


#define SIZE 100005
int n, e, dist[SIZE];
vector<ii> edgeList;
vector<int> adj[SIZE];


int shortest_path(){

    for(int i=1;i<=n;i++)
        dist[i] = MOD;
    priority_queue<ii> pq;
    dist[1] = 0;
    pq.push({0, 1});
    while(!pq.empty()){
        int v = pq.top().ss;
        int d = -pq.top().ff;
        pq.pop();
        if(dist[v] < d) continue;
        for(int e : adj[v]){
            int vv = v ^ edgeList[e].ff ^ edgeList[e].ss;
            int dd = d;
            if(dist[v] % 2 == 0){
                if(vv == edgeList[e].ss)    dd += 1;
                else    dd += 2;
            }
            else{
                if(vv == edgeList[e].ff)    dd += 1;
                else    dd += 2;
            }
            if(dd < dist[vv]){
                dist[vv] = dd;
                pq.push(ii (-dd, vv));
            }
        }
    }

    return dist[n];
}


int main(){

    int q;
    scanf("%d%d%d", &n, &e, &q);
    for(int i=0;i<e;i++){
        int a, b;
        scanf("%d%d", &a, &b);
        adj[a].pb(i);
        adj[b].pb(i);
        edgeList.pb({a, b});
    }

    int min_dist = shortest_path();
    while(q--){

        int t;
        scanf("%d", &t);
        if(t >= min_dist)   printf("GGMU\n");
        else    printf("FML\n");
    }

    return 0;
}

Second solution

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200005;
const int INF = 1500000000;
vector <int> G[MAXN];
int min_dist[MAXN];
void add_edge(int u, int v)
{
  G[u].push_back(v);
  G[v].push_back(u);
}
int main()
{
  int n,m,q;
  cin>>n>>m>>q;
  for (int i = 0; i < m; ++i)
  {
    int a,b;
    cin>>a>>b;
    add_edge(2*a, 2*b+1);
  }
  for (int i = 1; i <= n; ++i)
  {
    add_edge(2*i, 2*i+1);
    min_dist[2*i] = INF;
    min_dist[2*i+1] = INF;
  }
  queue <int> bfs;
  bfs.push(2);
  min_dist[2] = 0;
  while(!bfs.empty())
  {
    int top = bfs.front();
    bfs.pop();
    for (int i = 0; i < G[top].size(); ++i)
    {
      if(min_dist[G[top][i]] == INF)
      {
        min_dist[G[top][i]] = min_dist[top] + 1;
        bfs.push(G[top][i]);
      }
    }
  }
  int ans_time = min(min_dist[2*n], min_dist[2*n+1]);
  while(q--)
  {
    int t;
    cin>>t;
    if(ans_time <= t)
      cout<<"GGMU\n";
    else
      cout<<"FML\n";
  }
  return 0;
}