Problem Link: https://onlinejudge.org/external/105/10557.pdf

Hints:

Here are some important understandings to pick up from the problem statement while attempting to solve the problem. I struggled to some extent with catching up on the problem due to these facts 😓

1. Since the problem is directly related to energy consumption, we need to find the path with maximum cost(energy).
2. Another important factor is, here cost is not the edge cost. It’s the node’s cost. Notice that, it’s mentioned in the problem statement – “The energy value of this room is added to the player’s energy.” So, the usual edge cost storage of Bellman-Ford will not be implemented in this problem. So to track each node’s cost(rather than edge cost), I have taken a separate 1D vector named room_energy.
3. At any time while traveling, if the energy becomes <=0, and there is no other path, then immediately the result would be “hopeless” because it is not possible to go to another room with equal or less than 0 energy.
4. If the destination node can’t be reached using each edge once with >0 energy, then check for a positive cycle with the help of which(traversing that cycle repeatedly -> increasing energy enough to reach the destination node with >0 energy) the destination node can be reached with >0 energy.
5. While taking the edges as input, it would be wrong to assume that – “Always the last line of a particular test case would be 0 0. That is if the energy value for room i and the number of doorways leaving room i both are 0, then we should break the loop, that is the end of input taking for that case” – no, that’s not the case. Because any room i can have an energy value 0 and also no room can be reached from i. So even the first or second room can have 0 0 cases (0 energy, 0 rooms connected).

My solution idea and approach:

It’s evident that we’ll have to use Bellman-Ford here. So is only Bellman-Ford enough to solve this problem? 🤔 Let’s see.

We’ll have to start from node 1 and will have to reach node n. Also, after reaching the destination node n, the energy cannot be 0. Obviously, before reaching node n, energy can’t be 0, if so, the programs generate “hopeless” immediately.

Now, we’ll have to think, is node n connected to node 1? It’s very simple, only running Bellman-Ford will tell us that. How? While running Bellman-Ford, lastly we’ll return dis[n]. If the value is not updated from 0, that means that was not reached. Though the dis[n] can be 0 not just for the disconnectivity, but also due to total_energy being 0 after reaching node n. But that is not our concern how dis[n] is 0, as we’ll lastly check if dis[n] is not 0, then “winnable” should be printed.

Now, let’s consider the possibility of cycle/loop in the graph as a general Bellman-Ford would consider. In this problem, already it is evident that we would need to consider the positive cycles only. Because that can give us infinite energy(by repeatedly traversing the cycle) to reach the destination if and only if any node of the positive cycle is connected to the destination. Notice that, it is mentioned in the problem that we can repeat any path any number of times.

So two kinds of connectivity to check-

1. Whether node 1 is connected to node n. It doesn’t matter if any other nodes are not connected. For example, for n=5, a graph can be 1-3-5 2-4. Assuming energies between 1-3-5 are all >0, the output to this input would be “winnable”. Now, even if node 1 and node n are connected, the output would be “hopeless” if the only path to reach from 1 to n would result in <=0 energy. So for that scenario, we’ll have to check for a positive cycle.
2. If there is a positive cycle, whether any node of the cycle is connected to the destination node n. If that’s the case, then the output will definitely be “winnable”.

Now, the most intuitive idea can be –

1. At first, we’ll have to check whether node 1 is connected and reachable to node n or not. If yes, then winnable
2. If step 1 is NO, then we’ll have to look for positive cycles and then whether that cycle is connected to n. If yes, then winnable, otherwise hopeless.

If we think like this, then to address the first part, Bellman-Ford is enough by checking the value of dis[n]. For the 2nd part, we can detect a positive cycle inside the Bellman-Ford. But what about checking the connectivity of that cycle to the node n? One way could be – while checking the existence of the positive cycle inside Bellman-Ford, then store the nodes involved in the cycle in a set. And then checking for each node separately, whether those nodes are connected to the node n or not using DFS; that is to run the DFS code k th time if there are k nodes involved in the positive cycle. But this process seems much time-consuming, right? There might be a better way. 🤔

Let’s interchange the above 2 steps to solve the problem! 💡

1. At first, we’ll mark the nodes which are reachable from the destination node n using DFS.
2. Then we’ll use Bellman-Ford to check whether node 1 is connected to node n with >0 energy or not. Also simultaneously will look for positive cycles and then whether that cycle is connected to the destination node n. If any of the answers to these two simultaneous things is yes, then winnable, otherwise hopeless.

So in this approach, we are doing the same thing, just with less time-consuming than the previous approach 😊

Steps in a nutshell:

1. While creating the adjacency list adj for the input graph, create another adjacency list named adj_reverse. We’ll need that graph to mark the nodes which are reachable from the destination node.
2. Run DFS on adj_reverse to mark the nodes which are reachable from the destination node.
3. Run Bellman-Ford. If the destination node n is reachable from node 1 with >0 energy (dis[n] will give the result) or if there is a positive cycle and any node of the positive cycle is already visited (which we got from running the DFS on adj_reverse) and we return true immediately, that means the output would be “winnable”. Otherwise (the return is not true and dis[n] is <=0) the output would be “hopeless”.

Code:

#include <bits/stdc++.h>

using namespace std;

void dfs(int u, vector<vector<int> > &adj_reverse, vector<bool> &vis)
{
    vis[u]=1; // storing the connected nodes to the source node
    for(int i=0; i<adj_reverse[u].size(); i++)
    {
        int v=adj_reverse[u][i];
        if(!vis[v]) dfs(v, adj_reverse, vis);
    }
}

int bellman_ford(int node, vector<vector<int> > &adj, vector<int> &room_energy, vector<bool> &vis)
{
    vector<int> dis(node+1, 0);
    dis[1]=100;

    for(int i=0; i<node; i++)
    {
        for(int u=1; u<=node; u++)
        {
            for(int k=0; k<adj[u].size(); k++)
            {
                int v=adj[u][k];
                int cost=room_energy[v];

                if(dis[u] && dis[v]<dis[u]+cost)
                {
                    dis[v]=dis[u]+cost;
                }
            }
        }
    }

    //For checking positive cycle
    for(int u=1; u<=node; u++)
    {
        for(int k=0; k<adj[u].size(); k++)
        {
            int v=adj[u][k];
            int cost=room_energy[v];

            if(dis[u] && dis[v]<dis[u]+cost)
            {
                //whether any node of the positive cycle is connected to the destination node or not
                if(vis[v]) return true;
            }
        }
    }
    return dis[node];
}

int main()
{
//    freopen("in.txt","r",stdin);
//    freopen("out.txt","w",stdout);

    int n;
    while(cin>>n && n!=-1)
    {
        vector<vector<int> > adj(n+1), adj_reverse(n+1);
        vector<int> room_energy(n+1);
        for(int i=1; i<=n; i++)
        {
            int cost, from=i, num;
            cin>>cost>>num;

            room_energy[i]=cost;

            for(int j=0; j<num; j++)
            {
                int to;
                cin>>to;
                adj[from].push_back(to);
                adj_reverse[to].push_back(from);
            }
        }

        vector<bool> vis(n+1, 0);
        dfs(n, adj_reverse, vis); //Marking the connected nodes to the destination node in vis[]

        int result=bellman_ford(n, adj, room_energy, vis); //checking for cycle and the reachability
        if(result) cout<<"winnable"<<endl;
        else cout<<"hopeless"<<endl;
    }

    return 0;
}

Problem Link: https://onlinejudge.org/external/104/10449.pdf

Note: The fact that this problem falls under the Bellman-Ford – is the key point here. Because the amount the city authority gets is the subtraction of two integers can produce negative integers. And cubing them will definitely not change the sign of the result(which square would have done instead). Once you can figure out this, The problem is a straightforward implementation of the Bellman-Ford algorithm.

As a side note, I was getting the wrong answer repeatedly even if my code was passing all the test cases of UDebug. Then after changing the data type of the “dis” vector from int to long long int made the code “accepted” finally on the UVa online judge!

Code:

#include <bits/stdc++.h>

#define pii             pair<int, int>


/*---------------------------Graph Moves-----------------------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------------------------*/

using namespace std;

vector<long long int> bellman_ford(int node, int edge, vector<pair<pii, int> > &adj)
{
    vector<long long int> dis(node+1, INT_MAX);
    dis[1]=0;

    for(int i=0; i<node; i++)
    {
        for(int j=0; j<edge; j++)
        {
            int u=adj[j].first.first;
            int v=adj[j].first.second;
            int cost=adj[j].second;
            if(dis[u] != INT_MAX && dis[v] > dis[u]+cost)
            {
                dis[v]=dis[u]+cost;
            }
        }
    }
    //Running an extra loop to find out whether the graph contains any negative cycle loop or not
    for(int j=0; j<edge; j++)
    {
        int u=adj[j].first.first;
        int v=adj[j].first.second;
        int cost=adj[j].second;
        if(dis[u] != INT_MAX && dis[v] > dis[u]+cost)
        {
            dis[v]=INT_MAX; //Marking the nodes which will keep decreasing infinitly due to negative weight cycle
        }
    }
    return dis;
}

int main()
{
//    freopen("in.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);


    int t=0, node, edge;
    while(cin>>node)
    {
        vector<int> busyness(node+1);
        for(int i=1; i<=node; i++)
        {
            cin>>busyness[i];
        }
        cin>>edge;
        vector<pair<pii, int> > adj;
        for(int i=0; i<edge; i++)
        {
            int from,to,w,cost;
            cin>>from>>to;

            w=busyness[to]-busyness[from];
            cost=w*w*w;
            adj.push_back({{from, to}, cost});
        }

        vector<long long int> dis=bellman_ford(node, edge, adj);

        int q, dst;
        cin>>q;
        cout<<"Set #"<<++t<<endl;

        for(int i=0; i<q; i++)
        {
            cin>>dst;
            if(dis[dst]<3 || dis[dst]==INT_MAX)
            {
                cout<<"?"<<endl;
            }
            else
            {
                cout<<dis[dst]<<endl;
            }
        }
    }
    return 0;
}