Question

Cisco | OA Coding and Solutions | Set - 15 | 2022

Answer 1

Question 

cisco For this question:
In a weighted directed graph, you can find minimum distance between any pair of nodes in the graph by using Floyd-Warshall Algorithm with time complexity of O(V^3) where V is number of vertices in the graph. So we can compute this, and just get minimum of round trip between any pair of cities.
I don't know if a better solution exists though.

 

is standard Floyd Warshall algo. You run the algo over the graph, then for every pair of cities, find the round-trip cost and check if it is the minimum, if so then we consider that pair of cities as the answer. Below is the C++ code

 

#include <bits/stdc++.h>
using namespace std;
#define INF 999999
int main()
{
    int n, m, a, b, p;
    pair<int, int> cities;
    long mrtt = INT_MAX;
    cin >> n >> m;
    vector<vector<long>> dist(n, vector<long>(n, INF));
    for (int i = 0; i < n; i++)
        dist[i][i] = 0;
    while (m--)
    {
        cin >> a >> b >> p;
        dist[a][b] = p;
    }
    for (int k = 0; k < n; k++)
    {
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (dist[i][k] + dist[k][j] < dist[i][j])
                    dist[i][j] = dist[i][k] + dist[k][j];
            }
        }
    }
    for (int i = 0; i < n; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            if (dist[i][j] + dist[j][i] < mrtt)
            {
                mrtt = dist[i][j] + dist[j][i];
                cities = {i, j};
            }
        }
    }
    if (mrtt >= INF)
        cout << "1000000\n-1\n-1";
    else
        cout << mrtt << "\n"
             << cities.first << "\n"
             << cities.second;
}