CARPD - Editorial

PROBLEM LINK:

Practice
Div-2 Contest
Div-1 Contest

Author: Jatin Yadav
Tester: Rahul Dugar
Editorialist: Mohammed Ehab

DIFFICULTY:

MEDIUM

PREREQUISITES:

Dijkstra and Floyd-Warshall

PROBLEM:

There are N cities connected by uni-directional roads. You have a car with a petrol tank of capacity C_p and a diesel tank of capacity C_d. In some cities, you can refuel the petrol tank, and in some cities, you can refuel the diesel tank. The car uses one unit of fuel per unit distance. Given the cost of petrol and diesel, and the lengths of the roads, find the minimum amount of money you have to pay to get from city 1 to city N.

QUICK EXPLANATION:

Create a graph where each vertex represents the city you’re in, the amount of petrol you have, and the amount of diesel you have. Get rid of type-0 cities by running Floyd-Warshall first to turn them into direct paths. Allow fuel to be sold back in city N, allowing you to fill up your tanks immediately when you can, so that you reduce the number of vertices. Finally, reduce the number of edges by greedily finishing up whichever fuel you can fill back immediately when you arrive, picking the cheapest if you can fill back both.

EXPLANATION:

First, let’s build some infrastructure for our solution. Let’s run Floyd-Warshall to get the minimum distance from every city a to every city b. Then, add a direct road with that length from a to b. That clearly doesn’t change the answer, but it’ll prove very useful. Also, city N's type doesn’t matter, so let’s make it a type-3 city.

What’s the naiive solution? Our state depends only on the city we’re in, how much petrol we have, and how much diesel we have. So let’s create a graph where each node (c,p,d) corresponds to being in city c, with p units of petrol and d units of diesel in our tanks. Now, for each city i, you may be able to go from c to i (only if you have enough fuel.) Suppose you spend a units of petrol and d units of diesel. a and b must sum up to the distance between the city. Now, that changes your state from (c,p,d) to (i,p-a,d-b) and doesn’t cost anything. Also, you can buy a unit of fuel or a unit of diesel (if you’re in a city that allows so, and you have space in the tank.)

The answer to our problem is a direct application of Dijkstra’s algorithm to this graph. However, the graph has too many vertices and edges. You may have about n*C_p*C_d vertices, and each vertex adds about n*min(C_p,C_d) edges. We need to optimize this.

The first idea is: allow fuel to be sold back in city N. That doesn’t change the answer because selling fuel is equivalent to not buying it in the first place. How does that help? Well, whenever you’re in a city that allows you to buy, say, petrol, you can just fill the petrol tank to the max without worrying about the cost. You can always just sell the excess later. So if you’re in a type-1 or a type-2 city, you only need to store the states where one of the tanks is full. For type-3, you only need the state where both tanks are full. What about type-0? Here’s where the Floyd-Warshall trick first comes into play. You can just throw these cities! Any path from a to b that passes through them is still considered by just taking the direct edge from a to b.

Now, the number of vertices was reduced to around n*max(C_p,C_d). We can’t squeeze that any further, so maybe we can reduce the edges? When we moved from city c to city i, we tried every possible division of the amount of fuel between petrol and diesel. However, the following greedy strategy works: if you’re going to a petrol city, finish all your petrol first and then your diesel; if you’re going to a diesel city, finish all your diesel first; if you’re going to a type-3 city, finish the cheaper first. Basically, you finish whichever you can fill back immediately, and the cheaper if you can fill back both.

That may seem to change the answer. It seems like we’re forbidden from using diesel in a way to a petrol city, for example. However, the Floyd-Warshall trick comes into play again. The basic argument is that the petrol city is just in the middle of a path to maybe a diesel city, or a type-3 city (which we made include city N,) so the direct edge to these cities will consider finishing the diesel first if it’s better. You can formalize this argument via some careful case analysis.

Now, the total number of edges is around n^2*max(C_p,C_d), which is enough to run Dijkstra.

SOLUTIONS:

Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;
#define MX 300
int a[MX+5],dist[MX+5][MX+5],d[MX+5][MX+5][MX+5];
struct node
{
    int c,p,d;
    node(int c,int p,int d):c(c),p(p),d(d){}
    bool operator<(const node &b) const
    {
        return (c<b.c || (c==b.c && p<b.p) || (c==b.c && p==b.p && d<b.d));
    }
};
int main()
{
    int t;
    scanf("%d",&t);
    while (t--)
    {
        int n,m,cp,cd,pp,pd;
        scanf("%d%d%d%d%d%d",&n,&m,&cp,&cd,&pp,&pd);
        for (int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            for (int j=1;j<=n;j++)
            dist[i][j]=1e9;
            dist[i][i]=0;
        }
        a[n]=3;
        while (m--)
        {
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            dist[a][b]=c;
        }
        //Floyd-Warshall
        for (int k=1;k<=n;k++)
        {
            for (int i=1;i<=n;i++)
            {
                for (int j=1;j<=n;j++)
                dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);
            }
        }
        for (int i=1;i<=n;i++)
        {
            for (int j=0;j<=MX;j++)
            {
                for (int k=0;k<=MX;k++)
                d[i][j][k]=1e9;
            }
        }
        set<pair<int,node> > s;
        node init(1,(a[1]&1)? cp:0,(a[1]&2)? cd:0);
        s.insert({init.p*pp+init.d*pd,init});
        d[1][init.p][init.d]=init.p*pp+init.d*pd;
        int ans=1e9;
        while (!s.empty())
        {
            int cost=s.begin()->first;
            node cur=s.begin()->second;
            s.erase(s.begin());
            if (d[cur.c][cur.p][cur.d]!=cost)
            continue;
            if (cur.c==n)
            ans=min(ans,cost-cur.p*pp-cur.d*pd); //Sell the remaining fuel
            for (int i=1;i<=n;i++)
            {
                if (i==cur.c || !a[i] || cur.p+cur.d<dist[cur.c][i]) //Throw type-0 cities and cities you can't reach
                continue;
                node ns=cur;
                ns.c=i;
                if (a[i]==1 || (a[i]==3 && pp<=pd)) //Petrol city or petrol is cheaper, finish petrol first
                {
                    if (dist[cur.c][i]<=ns.p)
                    ns.p-=dist[cur.c][i];
                    else
                    {
                        ns.d-=(dist[cur.c][i]-ns.p);
                        ns.p=0;
                    }
                }
                else //Diesel city or diesel is cheaper, finish diesel first
                {
                    if (dist[cur.c][i]<=ns.d)
                    ns.d-=dist[cur.c][i];
                    else
                    {
                        ns.p-=(dist[cur.c][i]-ns.d);
                        ns.d=0;
                    }
                }
                int nc=cost;
                if (a[i]&1) //can buy petrol, fill the petrol tank
                {
                    nc+=(cp-ns.p)*pp;
                    ns.p=cp;
                }
                if (a[i]&2) //can buy diesel, fill the diesel tank
                {
                    nc+=(cd-ns.d)*pd;
                    ns.d=cd;
                }
                if (nc<d[ns.c][ns.p][ns.d])
                {
                    d[ns.c][ns.p][ns.d]=nc;
                    s.insert({nc,ns});
                }
            }
        }
        if (ans==1e9)
        ans=-1;
        printf("%d\n",ans);
    }
}
1 Like