3.The Flight Plan

Spoj Question

You are given flights route map of a country consisting of N cities and M undirected flight routes. Each city has an airport and each airport can work as layover. The airport will be in two states, Loading and Running. In loading state, luggage is loaded into the planes. In the running state, planes will leave the airport for the next city. All the airports will switch their states from Loading to Running and vice versa after every T minutes. You can cross a city if its airport state is running. Initially, all the airports are in running state. At an airport, if its state is loading, you have to wait for it to switch its state to running. The time taken to travel through any flight route is C minutes. Find the lexicographically smallest path which will take the minimum amount of time (in minutes) required to move from city X to city Y.

Solution: (Using BFS)

To Store the path: Maintain 2 arrays Predecessor and Distance

#include <bits/stdc++.h>

using namespace std;

void bfs(int node, int target, vector<int> v[], vector<bool> &vs, vector<int> &dist, vector<int> &pred)
{
    queue<int> q;
    q.push(node);
    vs[node] = 1;
    pred[node] = -1;
    while (!q.empty())
    {
        int x = q.front();
        int d = dist[x];
        q.pop();

        if (x == target)
        {
            return;
        }
        for (auto itr = v[x].begin(); itr != v[x].end(); itr++)
        {
            if (vs[*itr] == 0)
            {
                q.push(*itr);
                vs[*itr] = 1;
                dist[*itr] = d + 1;
                pred[*itr] = x;
            }
        }
    }
    return;
}

int main()
{
    vector<int> sol;
    int n, m, t, c;
    cin >> n >> m >> t >> c;

    vector<int> v[n + 1];
    vector<bool> vs(n + 1);
    vector<int> dist(n + 1);
    vector<int> pred(n + 1);
    for (int i = 1; i <= m; i++)
    {
        int a, b;
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }

    for (int i = 1; i <= n; i++)
    {
        sort(v[i].begin(), v[i].end());
    }
    int x, y;
    cin >> x >> y;

    bfs(x, y, v, vs, dist, pred);

    cout << dist[y] + 1 << "\n";

    sol.push_back(y);
    while (pred[y] != -1)
    {
        sol.push_back(pred[y]);
        y = pred[y];
    }

    for (int i = sol.size() - 1; i >= 0; i--)
    {
        cout << sol[i] << " ";
    }
    return 0;
}