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 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;
}