# HackerEarth Edge Destruction problem solution

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.

`#include <bits/stdc++.h>using namespace std;#define ll  long long int#define MOD 1000000007ll 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 350using 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;}`