0 like 0 dislike
725 views
| 725 views

0 like 0 dislike

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;
}``````
by Expert (113,040 points)