LightOJ 1049 - One Way Roads

Brief Description of the Problem

There are n cities and they were connected by n two-way roads in the ring in such way that each city was connected directly to exactly two other cities, and from each city it was possible to get to any other city. Government changed those two-way roads and made them one-way roads. Now, you are given those n one-way roads directions and also the cost with each road, you can change the direction of a road by the cost associated with it. You need to change the directions of the roads in such way so that from every city you can get to any other. What is the minimum amount of money by which you can do this?

Input

Input starts with an integer T (≤ 200), denoting the number of test cases.

Each case starts with a blank line and an integer n (3 ≤ n ≤ 100) denoting the number of cities (and roads). Next n lines contain description of roads. Each road is described by three integers ai, bi, ci (1 ≤ ai, bi ≤ n, ai ≠ bi, 1 ≤ ci ≤ 100) - road is directed from city ai to city bi, redirecting the direction/traffic costs ci.

Output

For each case of input you have to print the case number and the smallest amount of money the government should spend on the redirecting of roads so that from every city you can get to any other.

Solution

One crucial Observation is needed to solve this problem. As the cities are in a ring shape and the roads are in between them and also the roads are one-way, so we have only two ways by which we can make it possible to go any city from each city. We can either consider the circle/ring of the cities in clockwise or anti-clockwise. If we make all the roads in clockwise or anti-clockwise only then we can fulfil the conditions.

Now, we can get the amount of money for both of the ways and then take the minimum of them.

Implementation

We will use a two dimentional vector for storing the roads and a map for stroing the cost associated with a road, the key of the map will be the pair of the cities which is the endpoint of a road(according to the direction) and the value will be the cost associated with that road. We will store the roads in two dimensional vector as a two-way roads, because it will help us to check both clockwise and anti-clockwise with two for loops easily.

The code for taking the input is given below.

    int n;
    cin >> n;

    vector<int> adj[n+5];
    map<pair<int,int>, int> mp;

    for(int i = 1; i <= n; i++){
        int u, v, cost;
        cin >> u >> v >> cost;
        mp[{u, v}] = cost;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

First we will start from city 1 (you can start from any city), as we stored the roads as two-way in the vector so every city are directly connected two other roads. Let's consider adj[1][0] city is connected with city 1 in the clockwise path, and adj[1][1] city is connected in anti-clockwise path. As we have n roads so for both clockwise and anti-clockwise path we will use a for loop which will proceed n times. In both loops we will maintain two variables cur_city and next_city. The cur_city will represents the current city where we are in right now and the next_city will represents the city which is in the right side(during clockwise) or left side(during anti-clockwise) of the current city. For each iteration of the loop we will check whether there is a path between cur_city and next_city (by checking if(mp[{cur_city, next_city}] == 0)), if the condition is true then we need to redirect the road(because we need a road for going further in this path) thus we will add the redirecting cost of the road {next_city, cur_city} which is in mp[{next_city, cur_city}]. After that we will update the cur_city and next_city.

For clockwise path I considered cur_city = 1 and the next_city = adj[1][0], the code is given below for clockwise path.

    int ans1 = 0;

    int cur_city = 1, next_city = adj[1][0], temp;

    for(int i = 1; i <= n; i++){
        if(mp[{cur_city, next_city}] == 0) ans1 += mp[{next_city, cur_city}];

        temp = adj[next_city][0];
        if(temp == cur_city) temp = adj[next_city][1];

        cur_city = next_city;
        next_city = temp;
    }

For ant-clockwise path I considered cur_city = 1 and the next_city = adj[1][1], the code is given below for ant-clockwise path.

    int ans2 = 0;
    cur_city = 1;
    next_city = adj[1][1];

    for(int i = 1; i <= n; i++){
        if(mp[{cur_city, next_city}] == 0) ans2 += mp[{next_city, cur_city}];

        temp = adj[next_city][0];
        if(temp == cur_city) temp = adj[next_city][1];

        cur_city = next_city;
        next_city = temp;
    }

Finally the answer will be the minimum of ans1 and ans2.

Full Code in C++

#include <bits/stdc++.h>
using namespace std;

void solve(int t_case)
{
    int n;
    cin >> n;

    vector<int> adj[n+5];
    map<pair<int,int>, int> mp;

    for(int i = 1; i <= n; i++){
        int u, v, cost;
        cin >> u >> v >> cost;
        mp[{u, v}] = cost;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    int ans1 = 0;

    int cur_city = 1, next_city = adj[1][0], temp;

    for(int i = 1; i <= n; i++){
        if(mp[{cur_city, next_city}] == 0) ans1 += mp[{next_city, cur_city}];

        temp = adj[next_city][0];
        if(temp == cur_city) temp = adj[next_city][1];

        cur_city = next_city;
        next_city = temp;
    }

    int ans2 = 0;
    cur_city = 1;
    next_city = adj[1][1];

    for(int i = 1; i <= n; i++){
        if(mp[{cur_city, next_city}] == 0) ans2 += mp[{next_city, cur_city}];

        temp = adj[next_city][0];
        if(temp == cur_city) temp = adj[next_city][1];

        cur_city = next_city;
        next_city = temp;
    }

    cout << "Case " << t_case << ": " << min(ans1, ans2) << "\n";
}

int main()
{
    int tc = 1, t_case = 1;
    cin >> tc;
    while(tc--) solve(t_case++);

    return 0;
}

---

Tutorial source