Skip to content
Programmingoneonone
Programmingoneonone
  • Home
  • CS Subjects
    • Internet of Things (IoT)
    • Digital Communication
    • Human Values
  • Programming Tutorials
    • C Programming
    • Data structures and Algorithms
    • 100+ Java Programs
    • 100+ C Programs
  • HackerRank Solutions
    • HackerRank Algorithms Solutions
    • HackerRank C problems solutions
    • HackerRank C++ problems solutions
    • HackerRank Java problems solutions
    • HackerRank Python problems solutions
  • Work with US
Programmingoneonone
Programmingoneonone

HackerEarth Route Planning problem solution

YASH PAL, 31 July 2024
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

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;
}
coding problems solutions

Post navigation

Previous post
Next post

Related website

The Computer Science

Pages

  • About US
  • Contact US
  • Privacy Policy

Programing Practice

  • C Programs
  • java Programs

HackerRank Solutions

  • C
  • C++
  • Java
  • Python
  • Algorithm

Other

  • Leetcode Solutions
  • Interview Preparation

Programming Tutorials

  • DSA
  • C

CS Subjects

  • Digital Communication
  • Human Values
  • Internet Of Things
  • YouTube
  • LinkedIn
  • Facebook
  • Pinterest
  • Instagram
©2025 Programmingoneonone | WordPress Theme by SuperbThemes