HackerEarth Trustworthy network problem solution

In this HackerEarth Trustworthy network problem solution You are a secret agent of S.C.R.E.E.N., who infiltrated the evil organization called Hyena. You have discovered a vital information and want to send it from city s to city e via unidirectional telegraphs.

Unfortunately, you can’t trust anyone, so to be sure that the message was delivered and it is correct, you want to receive an acknowledgement message from city e. So if the message was sent through cities s = u1,u2,…,uk = e, then city e sends an acknowledgement message to uk-1, then uk-1 sends an acknowledgement message to and so on, until s receives acknowledgement message.

However, the telegraph lines only work in one direction, thus, the acknowledgement message may be sent back through any other cities. Moreover, for each telegraph line that can send messages from city u to city v there is an information about delivery cost for a single message.

Your task is to find the minimal cost it takes to send message from city s to city e and get an acknowledgement message, or output -1, if it’s impossible.

HackerEarth Trustworthy network problem solution.

#include <cstdio>
#include <algorithm>
int const INF = 1 << 30;
int const N = 333;
int a[N][N], b[N][N];
int main() {
  int n, m, st, fin;
  scanf("%d%d%d%d", &n, &m, &st, &fin);
  --st;
  --fin;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      a[i][j] = INF;
    }
    a[i][i] = 0;
  }
  for (int i = 0; i < m; i++) {
    int v, u, w;
    scanf("%d%d%d", &v, &u, &w);
    --v;
    --u;
    a[v][u] = w;
  }
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      b[i][j] = a[i][j];
    }
  }
  for (int k = 0; k < n; k++) {
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        if (b[i][k] == INF || b[k][j] == INF) continue;
        b[i][j] = std::min(b[i][j], b[i][k] + b[k][j]);
      }
    }
  }
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      if (b[j][i] != INF && a[i][j] != INF) {
        a[i][j] += b[j][i];
      } else a[i][j] = INF;
    }
  }
  for (int k = 0; k < n; k++) {
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        if (a[i][k] == INF || a[k][j] == INF) continue;
        a[i][j] = std::min(a[i][j], a[i][k] + a[k][j]);
      }
    }
  }
  printf("%dn", a[st][fin] == INF ? -1 : a[st][fin]);
}

Second solution

#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9 + 5;
const int nax = 305;
long long memo[nax][nax], d[nax][nax];
void floyd_warshall(int n) {
  for(int k = 1; k <= n; ++k)
    for(int i = 1; i <= n; ++i)
      for(int j = 1; j <= n; ++j)
        d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}
int main() {
  int n, m, start, end;
  scanf("%d%d%d%d", &n, &m, &start, &end);
  for(int i = 1; i <= n; ++i)
    for(int j = 1; j <= n; ++j)
      d[i][j] = i == j ? 0 : inf;
  while(m--) {
    int a, b, c;
    scanf("%d%d%d", &a, &b, &c);
    d[a][b] = c;
  }
  for(int i = 1; i <= n; ++i)
    for(int j = 1; j <= n; ++j)
      memo[i][j] = d[i][j];
  floyd_warshall(n);
  for(int i = 1; i <= n; ++i)
    for(int j = i + 1; j <= n; ++j) {
      auto tmp = d[i][j];
      d[i][j] = memo[i][j] + d[j][i];
      d[j][i] = memo[j][i] + tmp;
    }
  floyd_warshall(n);
  if(d[start][end] >= inf) d[start][end] = -1;
  printf("%lldn", d[start][end]);
}

HackerEarth Trustworthy network problem solution

HackerEarth Trustworthy network problem solution.

Second solution

Leave a Reply

Pages

Practice