HackerEarth Route Planning problem solution

In this HackerEarth Route Planning problem solution A city contains N stations. Also in the city circulate M buses. The i-th bus has an itinerary consisting of ti stations: s(i,1),s(i,2),…s(i,ti). At moment 0 it is at the station s(i,1), and then each minute he travels to the next station. When it reaches the end it goes back to the begging and starts again. At moment 0 you are at station 1.

If at any moment you and a bus are at the same station, you can get on it and travel with it. You can get off at any station. The same station can appear multiple times in the itinerary of the bus, but not adjacent to each other (in particular, the last station is adjacent to the first). You can only travel by bus. You are interested in finding the minimum amount of time you need to get to each station, or state that it is impossible.

You can only travel in one bus at a time, but you can use multiple buses to reach your destination. There can be multiple buses at the the same station at the same time. Getting in and off a bus is instantaneous.

HackerEarth Route Planning problem solution.

#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define dbg(x) cout << #x << '=' << x << 'n';
#define ll long long
#define pi pair<int,int>
#define pl pair<long long,long long>
#define lg length()
#define sz size()
#define pb push_back
#define MAXN 100005
#define INF 1000000005
#define LINF 1000000000000000005

int n,m,x,y,q,t,v[100005],ans[100005];

vector <int> p[100005];

vector <pi> g[100005];

set <pi> s;

void Find(int nod, int dist){
    ans[nod]=dist;
    v[nod]=1;
    for(pi i : g[nod]){
        int nxt=p[i.x][(i.y+1)%(p[i.x].sz)];
        if(v[nxt]) continue;
        int ndist=((dist-i.y+p[i.x].sz-1)/(p[i.x].sz))*(p[i.x].sz)+i.y+1;
        if(ndist<ans[nxt]){
            s.erase({ans[nxt],nxt});
            ans[nxt]=ndist;
            s.insert({ndist,nxt});
        }
    }
    if(s.size()){
        pi nxt=*(s.begin());
        s.erase(s.begin());
        Find(nxt.y, nxt.x);
    }
}

int32_t main(){
    ios_base :: sync_with_stdio(0); cin.tie(); cout.tie();
    cin >> n >> m;
    for(int i=1;i<=m;i++){
        cin >> t;
        for(int j=0;j<t;j++){
            cin >> x;
            p[i].pb(x);
            g[x].pb({i,j});
        }
    }
    for(int i=1;i<=n;i++){
        ans[i]=INF;
        s.insert({ans[i],i});
    }
    for(int i=2;i<=n;i++) ans[i]=INF,s.insert({INF,i});

    Find(1,0);

    for(int i=2;i<=n;i++){
        if(ans[i]==INF) cout << -1 << ' ';
        else cout << ans[i] << ' ';
    }
}

Second solution

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cassert>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

const int MAXN = 100000;
const long long INF = 1000000000000000000LL;

struct Edge
{
    int v, cycle, i;
    Edge() {}
    Edge(int v, int cycle, int i) : v(v), cycle(cycle), i(i) {}
};

vector<Edge> adj[MAXN];

void addEdge(int u, int v, int cycle, int i)
{
    assert(u != v);
    adj[u].push_back(Edge(v, cycle, i));
}

int main()
{
    int n, m;
    assert(scanf("%d%d", &n, &m) == 2);
    assert(1 <= n && n <= MAXN);
    assert(1 <= m && m <= MAXN);
    int sumT = 0;
    for (int i = 0; i < m; ++ i) {
        int t;
        assert(scanf("%d", &t) == 1);
        // assert(2 <= t && t <= n);
        sumT += t;
        assert(sumT <= 2 * MAXN);
        vector<int> route;
        for (int j = 0; j < t; ++ j) {
            int x;
            assert(scanf("%d", &x) == 1);
            assert(1 <= x && x <= n);
            -- x;
            route.push_back(x);
        }
        for (int j = 0; j < t; ++ j) {
            addEdge(route[j], route[(j + 1) % t], t, j);
        }
    }
    vector<int> dist(n, -1);
    vector<bool> mark(n, false);
    queue<int> q;
    q.push(0);
    dist[0] = 0;
    while (q.size()) {
        int u = q.front();
        q.pop();
        mark[u] = false;
        for (const Edge& edge : adj[u]) {
            int v = edge.v;
            int newDist = 0;
            if (dist[u] % edge.cycle <= edge.i) {
                newDist = dist[u] / edge.cycle * edge.cycle + edge.i + 1;
            } else {
                newDist = (dist[u] / edge.cycle + 1) * edge.cycle + edge.i + 1;
            }
            if (dist[v] == -1 || dist[v] > newDist) {
                dist[v] = newDist;
                if (!mark[v]) {
                    mark[v] = true;
                    q.push(v);
                }
            }
        }
    }

    for (int i = 1; i < n; ++ i) {
        printf("%d ", dist[i]);
    }

    return 0;
}

HackerEarth Route Planning problem solution

HackerEarth Route Planning problem solution.

Second solution

Leave a Reply

Pages

Practice