UVa – 10449 – Traffic

Arunima Mandal

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;
}

Leave a comment