Skip to content
Programmingoneonone
Programmingoneonone
  • Home
  • CS Subjects
    • IoT ? Internet of Things
    • Digital Communication
    • Human Values
  • Programming Tutorials
    • C Programming
    • Data structures and Algorithms
    • 100+ Java Programs
    • 100+ C Programs
  • HackerRank Solutions
    • HackerRank Algorithms Solutions
    • HackerRank C problems solutions
    • HackerRank C++ problems solutions
    • HackerRank Java problems solutions
    • HackerRank Python problems solutions
Programmingoneonone

HackerEarth Trustworthy network problem solution

YASH PAL, 31 July 2024
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

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]);
}
coding problems solutions

Post navigation

Previous post
Next post

Pages

  • About US
  • Contact US
  • Privacy Policy

Programing Practice

  • C Programs
  • java Programs

HackerRank Solutions

  • C
  • C++
  • Java
  • Python
  • Algorithm

Other

  • Leetcode Solutions
  • Interview Preparation

Programming Tutorials

  • DSA
  • C

CS Subjects

  • Digital Communication
  • Human Values
  • Internet Of Things
  • YouTube
  • LinkedIn
  • Facebook
  • Pinterest
  • Instagram
©2025 Programmingoneonone | WordPress Theme by SuperbThemes