Join Us
Gives Memory Limit Exceeded.
Entering edit mode
Click here to Practice
Submit Problem to OJ
An Online Taxi service is facing losses due to recent changes in its discount prices. To overcome the losses, the team has made a list of M places of a city with N routes. Each route has 3 components.
The first component is the pick-up position id, the second is the destination position id and the third is the cost per trip between the pickup and destination. If cost is +ve, company is making a profit else loss from that trip. If the pick-up and destination point are same, then that trip is known as a round trip. Write an algorithm for the company's system that will calculate the maximum amount of money that they are losing in a round trip. Constraints: totalRoutes <= 1e4 , 0<= pickup/destination position <= 1e4, -1e3 <= cost <= 1e3 .
Example: 4 5 {0 1 -1} , {1 2 -2}, {2 0 -5}, {0 3 6}, {3 2 3}
output: -8 (in this case any of the following works: pickup/drop = (0,0/1,1/2,2).
Entering edit mode
Q1 solution
Overview
Given a weighted directed graph, you have to find the minimum weight of round trip, ( a round trip refers to loop).
Approach
The problem is a just an application of Topological Sorting, only difference is we don't have to find the topological sort instead we have to keep track of every loop.
Whenever we get a loop, sum up all the edges of the loop and keep track of minimum sum.
Complexity
O(n+m) as we are using a simple dfs.
Implementation
void dfs_cycle(int u, int p,int w, int color[], vector<pair<int,int>>& par, int& cyclenumber)
{
if (color[u] == 2) {
return;
}
if (color[u] == 1) {
int val =0;
vector<int> v;
cyclenumber++;
int cur = p;
val+=w;
// backtrack the vertex which are
// in the current cycle thats found
while (cur != u) {
val+=par[cur].second;
cur = par[cur].first;
}
ans = min(ans,val);
return;
}
par[u] = {p,w};
color[u] = 1;
// simple dfs on graph
for (pair<int,int> v : graph[u]) {
dfs_cycle(v.first, u,v.second, color, par, cyclenumber);
}
// completely visited.
color[u] = 2;
}
Entering edit mode
int bfs(int node, map<int, vector<pair<int, int>>> &adj)
{
int in = 0;
for (auto i : adj)
{
for (auto j : i.second)
{
if (j.first == node)
{
in++;
}
}
}
queue<pair<int, int>> q;
q.push({0, node});
int c = -1;
int ans = INT_MAX;
while (!q.empty())
{
int num = q.front().second;
int dist = q.front().first;
q.pop();
if (num == node)
{
c++;
ans = min(ans, dist);
if (c == in)
{
return ans;
}
}
for (auto i : adj[num])
{
int next = i.first;
int wt = i.second;
q.push({wt + dist, next});
}
}
return 0;
}
int f(vector<vector<int>> &edges, int n, int m)
{
map<int, vector<pair<int, int>>> adj;
for (auto i : edges)
{
adj[i[0]].push_back({i[1], i[2]});
}
int ans = INT_MAX;
for (int i = 0; i < n; i++)
{
ans = min(ans, bfs(i, adj));
}
return ans;
}
Entering edit mode
int bfs(int node, map>> &adj) { int in = 0; for (auto i : adj) { for (auto j : i.second) { if (j.first == node) { in++; } } } queue> q; q.push({0, node}); int c = -1; int ans = INT_MAX; while (!q.empty()) { int num = q.front().second; int dist = q.front().first; q.pop(); if (num == node) { c++; ans = min(ans, dist); if (c == in) { return ans; } } for (auto i : adj[num]) { int next = i.first; int wt = i.second; q.push({wt + dist, next}); } } return 0; } int f(vector> &edges, int n, int m) { map>> adj; for (auto i : edges) { adj[i[0]].push_back({i[1], i[2]}); } int ans = INT_MAX; for (int i = 0; i < n; i++) { ans = min(ans, bfs(i, adj)); } return ans; }
Loading Similar Posts
@Rishabh Verma, Why we need to call dfs with starting vertex 1 and not zero? I submitted my code with dfs from 0 and it got WA on test 4, then I saw some accepted codes and found that dfs has been called from "1". I'm unable to find any reason for the same, please help me with this.
You don't have to call dfs_cycle for node 1 or node 0 alone.
So how do you call a DFS: you iterate over every unvisited node and call DFS from there. So you have to call dfs_cycle for every unvisited node till now but not only for 0 or 1 alone. Its just by chance that you are getting accepted for only node 1, because random test cases were generated accordingly. I have updated the test cases...