Practice Link
Abhijeet and his challenging race
Author: mr_cchef
Editorialist: mr_cchef
Tester: dragno99
DIFFICULTY:
Easy-medium
PREREQUISITES:
Graph Theory, Dijkstra, Dynamic Programming
PROBLEM:
There are K cars starting at K different nodes and we have to calculate the node that will reach the destination node in the minimum amount of time considering we a car has a C unit fuel capacity and 1 unit of fuel is required to travel 1 unit distance.
There are also P fuel stations from where fuel can be refilled in the car in a negligible amount of time.
If the winner exists you have to print the node number of the car and in case of collision, the car with the minimum node number will be the winner.
If there is no winner then print -1.
QUICK EXPLANATION:
Instead of traveling from K starting nodes, we can start from the destination node and calculate the minimum distance required to reach those K nodes.
For calculating the shortest distance from node N to other we can use the Dijkstra algorithm.
Since we also have to manage the remaining fuel in the car, we have to modify the Dijkstra with a little touch of dynamic programming.
EXPLANATION:
Before reading the below editorial, I hope you are familiar with the prerequisites.
Approach 1:
You pick each starting node one by one and calculate the minimum distance to reach node N. Then, pick the node which has the shortest distance and if there are multiple then pick the lowest node. But this way the time complexity would be K * TC ( Dijkstra ) and i.e. K * (N * C+E * ClogN*C) but this would exceed the time limit.
Approach 2:
We will think in the reverse order. We will pick the destination node and try to calculate the minimum distance from the destination node to all other nodes. This way we do not need to run Dijkstra for k times.
Que: Why would the reverse approach work as we have a remaining fuel variable which is not necessarily the same at a particular node if we are traveling according to approach 1 and traveling according to approach 2.
1 → 2 → 3 → 4
Ans: Let’s say node 1 is the starting node and 4 is the destination node and 2 and 3 do not contain any fuel station. Now, if we start from 1 and initially the fuel tank is full and we are able to reach the destination then its converse is also true as we know distance remains constant.
With the same logic we can consider each fuel station as the starting node because, at that node, the fuel capacity of the car is full. Now, we can exploit the idea and starting from the destination node having full fuel capacity, try to reach the next fuel station and then from the fuel station to the next fuel station through the different path possible until we visit all the nodes or fuel is no more to continue traveling.
Now, we know at a particular node, we can reach with multiple remaining fuels of the car (through different paths) and it is possible that the remaining fuel of the car with the minimum distance traveled path would not be able to continue anymore because it now has insufficient fuel to reach to the next node so, and there exist some other path ending at the same node and has the sufficient fuel to reach next node but the path distance is not minimum, then we have to consider that path as this path will help to complete the race and might even win.
Considering all the above points, we need to modify the Dijkstra.
Simultaneously refer to the code for better understanding.
First of all, in a particular state three things are important
- Current node number
- Total distance covered
- Remaining fuel in the car
And one entry of the priority queue would contain these three value
Along with the ‘dist’ array (for storing the minimum distance to reach the node), we will also have a fuel array that would store the remaining fuel in the car for the minimum distance path.
A visited array of size N*C would help us to recognize whether we have reached a node ‘x’ with renaming the ‘y’ amount of fuel. If We have already visited, there is no need for that entry to process again, so we will skip it.
Fuel array would help us to compare the remaining fuel of the other paths.
Let’s say the current node is ‘u’ and distance traveled till the node is ‘distanceTravelled’ and current fuel is ‘fuelRemaining’ and we are exploring its neighbor ‘v’ with an edge weight ‘w’ and newFuelRemaining = fuelRemaining - w
Now, for adding an appropriate entry into the priority queue, we have three condition
-
dist[v]>distanceTravelled+w && newFuelRemaining>=0
The new distance to reach node v is less than the previous minimum distance considering it has sufficient fuel so that can reach node v through u.
In this case, we will perform relaxation and add the new entry into the priority queue and also update the remaining fuel at node v -
dist[v]==distanceTravelled+w && fuel[v]<newFuelRemaining
The new distance is equal to the minimum distance then we will check whether the current remaining fuel is greater than or not than newFuelRemaining.
If it is greater than the previous one, then we update the remaining fuel. -
dist[v]<distanceTravelled+w && fuel[v]<newFuelRemaining
New path distance is greater than previous but now the new remaining fuel though the current edge is greater than the remaining fuel in the minimum path.
In this case, we have to consider the path and add an entry into the priority queue
After performing the above mentioned Dijkstra, we can now compare the final minimum distance for all the cars to reach the destination node N and print the appropriate answer.
Time Complexity:
O(C*(N+Elog(N*C)))
Setter's Solution (C++)
//LinkedIn:https://www.linkedin.com/in/abhijeettamrakar/
//GitHub:https://github.com/mrcchef/
#include <bits/stdc++.h>
using namespace std;
#define fastio ios_base::sync_with_stdio(false); cin.tie(0) ; cout.tie(0);
#define ll long long
#define pb push_back
#define pii pair<ll,ll>
#define vi vector<ll>
#define endl "\n"
const ll inf=1e18;
const ll N=1e3+5;
vector<vector<pii>> g(N);
vi dist(N,inf);
vi fuel(N,0);
// Time complexity C*(N + ElogN*C)
void dijkstra(ll src,ll n,ll c,vi &isPetrolStation)
{
priority_queue<vi,vector<vi>,greater<vi>> pq;
vector<vi> visited(n+1,vi(c+1,0));
pq.push({0,src,c}); // distanceTravelled, node, fuel left
dist[src]=0;
while(!pq.empty())
{
vi node=pq.top();
pq.pop();
ll u=node[1];
ll distanceTravelled=node[0];
ll fuelRemaining=node[2];
if(visited[u][fuelRemaining])
continue;
visited[u][fuelRemaining]=true;
for(auto nbr:g[u])
{
ll v=nbr.first;
ll w=nbr.second;
ll newFuelRemaing=fuelRemaining-w;
if(dist[v]>distanceTravelled+w && newFuelRemaing>=0)
{
dist[v]=distanceTravelled+w;
fuel[v]=newFuelRemaing;
if(isPetrolStation[v])
fuel[v]=c;
pq.push({dist[v],v,fuel[v]});
}
else if(dist[v]==distanceTravelled+w && fuel[v]<newFuelRemaing)
{
fuel[v]=newFuelRemaing;
pq.push({dist[v],v,fuel[v]});
}
else if(dist[v]<distanceTravelled+w && fuel[v]<newFuelRemaing)
pq.push({distanceTravelled+w,v,newFuelRemaing});
}
}
}
void solve()
{
ll n,m,i,k,c,p;
cin>>n>>m>>k>>c>>p;
vi participants(k);
vi isPetrolStation(n+1,0);
for(i=0;i<m;i++)
{
ll x,y,w;
cin>>x>>y>>w;
g[x].pb({y,w});
g[y].pb({x,w});
}
for(i=0;i<k;i++)
cin>>participants[i];
for(i=0;i<p;i++)
{
ll x;
cin>>x;
isPetrolStation[x]=1;
}
dijkstra(n,n,c,isPetrolStation);
ll minDistanceNode=-1;
ll minDistance=inf;
for(i=0;i<k;i++)
{
if(minDistance>dist[participants[i]])
{
minDistance=dist[participants[i]];
minDistanceNode=participants[i];
}
}
cout<<minDistanceNode<<endl;
}
int main()
{
fastio
solve();
return 0;
}
Tester's Solution (Python)
from queue import PriorityQueue
[n, m, k, c, p] = (int(x) for x in input().split())
g = list([])
dp = list([])
station = list([])
for i in range(n+1):
g.append(list([]))
curr = list([])
for j in range(c+1):
curr.append(1e18)
dp.append((curr))
station.append(0)
for _ in range(m):
[x, y, w] = (int(x) for x in input().split())
g[x].append(([y , w]))
g[y].append(([x , w]))
racer = list(map(int , input().split()))
if p>0:
temp = list(map(int , input().split()))
for i in temp:
station[i] = 1
q = PriorityQueue()
q.put((0 , 0 , n))
visited=list([])
for i in range(0,n+1):
visited.append(0)
while not q.empty():
(cost, curr_fuel, node) = q.get()
if visited[node]:
continue
visited[node]=1
dp[node][curr_fuel] = cost
for j in range(curr_fuel , c+1 , 1):
dp[node][j] = min(dp[node][j] , dp[node][curr_fuel])
if station[node]:
curr_fuel = 0
for (child , weight) in g[node]:
if curr_fuel + weight <= c and cost + weight < dp[child][curr_fuel + weight]:
dp[child][curr_fuel + weight] = cost + weight
q.put(( cost + weight ,curr_fuel + weight , child ))
ans = [1e18 , 1e18]
for i in racer:
ans = min(ans , [ dp[i][c] , i ])
if ans[0] == 1e18:
print(-1)
else:
print(ans[1])