In this HackerEarth Edge Destruction problem solution Given a graph having N vertices and M bidirectional edges, with each edge having some length and some destruction cost. You have to increase the length of the shortest path between vertex 1 and vertex N, for that you can destroy some edges. Find the minimum cost of doing it.


HackerEarth Edge Destruction problem solution in java python c++ c and javascript programming with practical program code example and explanation


HackerEarth Edge Destruction problem solution.

#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD 1000000007
ll pow_mod(ll a, ll b, ll mod) {
ll res = 1;
while(b) {
if(b & 1) {
res = (res * a) % mod;
}
a = (a * a) % mod;
b >>= 1;
}
return res;
}
const int maxn = 1000;
vector < int > adj[maxn + 5];
vector < pair < int, int > > adj1[maxn + 5];
vector < pair < pair < int, int >, pair < int, int > > > edges;
int cap[maxn + 5][maxn + 5];
int residual_network_cap[maxn + 5][maxn + 5];
int prev_nd[maxn + 5];
int flow_intermediate[maxn + 5];
void update_residual(int v, int flow) {
while(v != prev_nd[v]) {
residual_network_cap[prev_nd[v]][v] += flow;
residual_network_cap[v][prev_nd[v]] -= flow;
v = prev_nd[v];
}
}
int find_augment_path_flow(int src, int snk, int n) {
for(int i = 0; i <= n; ++i) {
prev_nd[i] = -1;
flow_intermediate[i] = 0;
}
queue < int > q;
q.push(src);
prev_nd[src] = src;
flow_intermediate[src] = (int)(1e8);
while(!q.empty()) {
int nd = q.front();
q.pop();
if(nd == snk) {
return flow_intermediate[nd];
}
for(int i = 0; i < (int)(adj[nd].size()); ++i) {
int to = adj[nd][i];
if((cap[nd][to] <= residual_network_cap[nd][to]) || (prev_nd[to] != -1)) {
continue;
}
flow_intermediate[to] = min(flow_intermediate[nd], cap[nd][to] - residual_network_cap[nd][to]);
q.push(to);
prev_nd[to] = nd;
}
}
return 0;
}
int compute_max_flow(int src, int snk, int n) {
memset(residual_network_cap, 0, sizeof(residual_network_cap));
int cur_flow;
int final_flow = 0;
while((cur_flow = find_augment_path_flow(src, snk, n))) {
final_flow += cur_flow;
update_residual(snk, cur_flow);
}
return final_flow;
}
vector < int > dijkstra(int src, int n) {
vector < int > dist;
dist.resize(n + 1, INT_MAX);
priority_queue < pair < int, int > > pq;
dist[src] = 0;
pq.push(make_pair(0, src));
while(!pq.empty()) {
pair < int, int > tp = pq.top();
pq.pop();
int local_nd = tp.second;
int local_dist = -1 * tp.first;
if(local_dist > dist[local_nd]) {
continue;
}
for(int i = 0; i < (int)(adj1[local_nd].size()); ++i) {
int nd = adj1[local_nd][i].first;
int nd_dist = adj1[local_nd][i].second;
if(dist[nd] > nd_dist + local_dist) {
dist[nd] = nd_dist + local_dist;
pq.push(make_pair(-1 * dist[nd], nd));
}
}
}
return dist;
}
int main() {
int n, m;
cin >> n >> m;
assert(1 <= n && n <= 1000);
assert(1 <= m && m <= 400000);
int x, y, w, c;
for(int i = 1; i <= m; ++i) {
cin >> x >> y >> w >> c;
assert(1 <= x <= n);
assert(1 <= y <= n);
assert(1 <= w <= 1000000);
assert(1 <= c <= 1000000);
adj1[x].push_back(make_pair(y, w));
adj1[y].push_back(make_pair(x, w));
edges.push_back(make_pair(make_pair(x, y), make_pair(w, c)));
edges.push_back(make_pair(make_pair(y, x), make_pair(w, c)));
}
memset(residual_network_cap, 0, sizeof(residual_network_cap));
memset(cap, 0, sizeof(cap));
vector < int > dist1 = dijkstra(1, n);
vector < int > dist2 = dijkstra(n, n);
for(int i = 1; i <= (int)(edges.size()); ++i) {
int u = edges[i].first.first;
int v = edges[i].first.second;
int wt = edges[i].second.first;
int cst = edges[i].second.second;

if(dist1[n] == (dist1[u] + wt + dist2[v])) {
adj[u - 1].push_back(v - 1);
adj[v - 1].push_back(u - 1);
cap[u - 1][v - 1] += cst;
}
}
cout << compute_max_flow(0, n - 1, n) << endl;
return 0;
}

Second solution

#include <fstream>
#include <iostream>
#include <string>
#include <complex>
#include <math.h>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <stdio.h>
#include <stack>
#include <algorithm>
#include <list>
#include <ctime>

#include <memory.h>
#include <assert.h>

#define y0 sdkfaslhagaklsldk

#define y1 aasdfasdfasdf
#define yn askfhwqriuperikldjk
#define j1 assdgsdgasghsf
#define tm sdfjahlfasfh
#define lr asgasgash
#define norm asdfasdgasdgsd
#define have adsgagshdshfhds

#define eps 1e-6
#define M_PI 3.141592653589793
#define bs 1000000007
#define bsize 350

using namespace std;

const int INF = 1e9;
const int N = 600000;

int n, m;
int a[N], b[N], c[N], d[N];
int D1[N], D2[N];
int dist[N];
int cost1, cost2;
int used[N];
vector<int> g[N];

void trace_distances(int start)
{
for (int i = 1; i <= n; i++)
{
used[i] = 0;
dist[i] = 1e9;
}
dist[start] = 0;
for (int iter = 1; iter <= n; iter++)
{
int best_dist = 2e9;
int best_id = -1;
for (int i = 1; i <= n; i++)
{
if (used[i])
continue;
if (dist[i] < best_dist)
{
best_dist = dist[i];
best_id = i;
}
}
used[best_id] = 1;
for (int j = 0; j < g[best_id].size(); j++)
{
int id = g[best_id][j];
int to;
if (a[id] == best_id)
to = b[id];
else
to = a[id];
dist[to] = min(dist[to], dist[best_id] + d[id]);
}
}
}

int s, t;
int res;

struct edge
{
int a;
int b;
int cap;
int flow;
};

int ptr[N];
vector<edge> e;
vector<int> G[N];
int D[N];

void add_edge(int a, int b, int cap)
{
edge e1 = { a, b, cap, 0 };
edge e2 = { b, a, 0, 0 };
G[a].push_back(e.size());
e.push_back(e1);
G[b].push_back(e.size());
e.push_back(e2);
}

bool bfs()
{
queue < int> qu;
for (int i = 0; i <= n; i++)
{
D[i] = -1;
}
//cout << "!" << endl;
qu.push(s);
D[s] = 0;
while (qu.size())
{
int v = qu.front();
qu.pop();
for (int i = 0; i < G[v].size(); i++)
{
int id = G[v][i];
if (e[id].flow == e[id].cap)
continue;
int to = e[id].b;
if (D[to] != -1)
continue;
D[to] = D[v] + 1;
qu.push(to);
}
}
return D[t] != -1;
}

int dfs(int v, int flow)
{
if (v == t || flow == 0)
return flow;
for (; ptr[v] < G[v].size(); ptr[v]++)
{
int id = G[v][ptr[v]];
int to = e[id].b;
if (D[to] != D[v] + 1)
continue;
int pushed = dfs(to, min(flow, e[id].cap-e[id].flow));
if (pushed)
{
e[id].flow += pushed;
e[id ^ 1].flow -= pushed;
return pushed;
}
}
return 0;
}

int dinic()
{
int flow = 0;
while (true)
{
if (!bfs())
break;
for (int i = 0; i <= n; i++)
{
ptr[i] = 0;
}
while (true)
{
int pushed = dfs(s, 1000000000);
if (pushed == 0)
break;
flow += pushed;
}
}
return flow;
}

int main(){
ios_base::sync_with_stdio(0);
//cin.tie(0);

cin >> n >> m;
for (int i = 1; i <= m; i++)
{
cin >> a[i] >> b[i] >> d[i] >> c[i];
g[a[i]].push_back(i);
g[b[i]].push_back(i);
}

trace_distances(1);
for (int i = 1; i <= n; i++)
{
D1[i] = dist[i];
}
trace_distances(n);
for (int i = 1; i <= n; i++)
{
D2[i] = dist[i];
}

for (int i = 1; i <= m; i++)
{
if (D1[a[i]] > D1[b[i]])
swap(a[i], b[i]);

if (D2[b[i]] + D1[a[i]] + d[i] == D1[n])
{
add_edge(a[i], b[i], c[i]);
}
}

s = 1;
t = n;
res = dinic();
cout << res << endl;

cin.get(); cin.get();
return 0;
}