HackerEarth The Flight Plan problem solution

In this HackerEarth The Flight Plan problem solution 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.

It is guaranteed that the given flight route map will be connected. Graph won’t contain multiple edges and self loops. A self loop is an edge that connects a vertex to itself.

HackerEarth The Flight Plan problem solution.

#include <bits/stdc++.h>

#define ll long long
#define ull unsigned long long
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define be begin()
#define en end()
#define all(x) (x).begin(),(x).end()
#define alli(a, n, k) (a+k),(a+n+k)
#define REP(i, a, b, k) for(__typeof(a) i = a;i < b;i += k)
#define REPI(i, a, b, k) for(__typeof(a) i = a;i > b;i -= k)
#define REPITER(it, a) for(__typeof(a.begin()) it = a.begin();it != a.end(); ++it)

#define y0 sdkfaslhagaklsldk
#define y1 aasdfasdfasdf
#define yn askfhwqriuperikldjk
#define j1 assdgsdgasghsf
#define tm sdfjahlfasfh
#define lr asgasgash
#define norm asdfasdgasdgsd
#define have adsgagshdshfhds

#define eps 1e-6
#define pi 3.141592653589793

using namespace std;

template<class T> inline T gcd(T a, T b) { while(b) b ^= a ^= b ^= a %= b; return a; }
template<class T> inline T mod(T x) { if(x < 0) return -x; else return x; }

typedef vector<int> VII;
typedef vector<ll> VLL;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef pair<int, PII > PPII;
typedef vector< PII > VPII;
typedef vector< PPII > VPPI;

const int MOD = 1e9 + 7;
const int INF = 1e9;

const int MAX = 1e5 + 5;
VII adj[MAX], v;
bool vis[MAX];
VII parent[MAX];
int time1[MAX];

void bfs (int n, int c, int t) {
    queue <int> q;
    PII p;
    int s;
    q.push(1);
    time1[1] = 0;
    vis[1] = true;
    while(!q.empty()) {
        s = q.front();
        q.pop();
        for (int to:adj[s]) {
            if (vis[to] == false or time1[to] >= time1[s] + c) {
                parent[to].pb(s);
                if (time1[to] >= time1[s] + c) continue;
                vis[to] = true;;
                time1[to] = time1[s] + c;
                q.push(to);
            }
        }
    }
}

void dfs(int x, VII v1) {
    v1.pb(x);
    if (x == 1) {
        reverse(all(v1));
        if (v1 < v or v.size() == 0) v = v1;
    }
    for (int to:parent[x]) {
        dfs(to, v1);
    }
}

int main(int argc, char* argv[])
{
    if(argc == 2 or argc == 3) freopen(argv[1], "r", stdin);
    if(argc == 3) freopen(argv[2], "w", stdout);
    ios::sync_with_stdio(false);
    int n, m, t, c, u, v2;
    cin >> n >> m >> t >> c;
    for (int i = 0; i < m; i++) {
        cin >> u >> v2;
        adj[u].push_back(v2);
        adj[v2].push_back(u);
    }

    bfs(n, c, t);
    VII v1;
    dfs(n, v1);
    reverse(all(v));
    cout << v.size() << endl;
    REPI(i, (int)v.size()-1, -1, 1) {
        cout << v[i];
        if (i == 0) cout << endl;
        else cout << ' ';
    }
    return 0;
}

Second solution

#include<bits/stdc++.h>
using namespace std;
vector<int>v[1005];
bool vis[1005];
int tim[1005],from[1005];
int n,m,t,c;
void bfs(int s,int end)
{
    queue<int>q;
    q.push(s);vis[s]=1;
    while(!q.empty())
    {
        int u=q.front();q.pop();
        for(auto i:v[u])
        {
            if(!vis[i])
            {
                from[i]=u;vis[i]=1;
                if(i==end)return;
                q.push(i);
            }
        }
    }
}
int main()
{
    cin>>n>>m>>t>>c;
    assert(n>=1 && n<=1e3);
    assert(m>=n-1 && m<=n*(n-1)/2);
    assert(t>=1 && t<=1e3);
    assert(c>=1 && c<=1e3);
    if(n==1){cout<<"1n1";return 0;}
    for(int i=1;i<=m;i++)
    {
        int x,y;
        cin>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    int x,y;
    cin>>x>>y;
    for(int i=1;i<=n;i++)sort(v[i].begin(),v[i].end());
    bfs(x,y);
    vector<int>ans;ans.push_back(y);
    int s=from[y],cnt=1;
    while(s!=x)
    {
        ans.push_back(s);
        s=from[s];cnt++;
    }
    ans.push_back(x);cnt++;cout<<cnt<<"n";
    for(int i=ans.size()-1;i>=0;i--)cout<<ans[i]<<" ";
    return 0;
}

HackerEarth The Flight Plan problem solution

HackerEarth The Flight Plan problem solution.

Second solution

Leave a Reply

Pages

Practice