HackerRank Going to the Office Problem Solution Yashwant Parihar, June 2, 2023May 28, 2024 In this post, we will solve HackerRank Going to the Office Problem Solution. Ms.Kox enjoys her job, but she does not like to waste extra time traveling to and from her office. After working for many years, she knows the shortest-distance route to her office on a regular day. Recently, the city began regular maintenance of various roads. Every day a road gets blocked and no one can use it that day, but all other roads can be used. You are Ms. Kox’s new intern and she needs some help. Every day, you need to determine the minimum distance that she has to travel to reach her office. Input Format There are N cities numbered 0 to N-1 and M bidirectional roads. The first line of the input contains two integers N and M. M lines follow, each containing three space-separated integers u , v and w, where u and v are cities connected by a bi-directional road and w is the length of this road. There is at most one road between any two cities and no road connects a city to itself. The next line contains two integers S and D. S is the city where Ms. Kox lives and D is the city where her office is located. The next line contains an integer Q, the number of queries. Q lines follow, each containing two integers u and v, where the road between u and v has been blocked that day. Output Format Output Q lines, with each line containing the minimum distance Ms.Kox has to travel on that day. If there is no path, print “Infinity“. Sample Input 6 9 0 1 1 1 2 1 2 3 1 3 4 1 4 5 1 2 4 5 3 5 8 1 3 3 0 2 4 0 5 9 0 1 1 2 2 3 3 4 4 5 2 4 3 5 1 3 0 2 Sample Output 7 6 6 8 11 5 5 5 5 HackerRank Going to the Office Problem Solution Going to the Office C Solution #include<stdio.h> #include<stdlib.h> typedef struct { int u; long long w; }node; void merge(long long *a, long long *left_a, long long *right_a, int left_size, int right_size) { int i = 0, j = 0; while( i < left_size || j < right_size ) { if( i == left_size ) { a[i + j] = right_a[j]; j++; } else if( j == right_size ) { a[i + j] = left_a[i]; i++; } else if( left_a[i] <= right_a[j] ) { a[i + j] = left_a[i]; i++; } else { a[i + j] = right_a[j]; j++; } } return; } void sort_a(long long *a, int size) { if( size < 2 ) { return; } int m = ( size + 1 ) / 2, i; long long *left_a, *right_a; left_a = (long long*)malloc(m * sizeof(long long)); right_a = (long long*)malloc(( size - m ) * sizeof(long long)); for( i = 0 ; i < m ; i++ ) { left_a[i] = a[i]; } for( i = 0 ; i < size - m ; i++ ) { right_a[i] = a[i + m]; } sort_a(left_a, m); sort_a(right_a, size - m); merge(a, left_a, right_a, m, size - m); free(left_a); free(right_a); return; } void merge2(int *a, int *left_a, int *right_a, int *b, int *left_b, int *right_b, int left_size, int right_size) { int i = 0, j = 0; while( i < left_size || j < right_size ) { if( i == left_size ) { a[i + j] = right_a[j]; b[i + j] = right_b[j]; j++; } else if( j == right_size ) { a[i + j] = left_a[i]; b[i + j] = left_b[i]; i++; } else if( left_a[i] <= right_a[j] ) { a[i + j] = left_a[i]; b[i + j] = left_b[i]; i++; } else { a[i + j] = right_a[j]; b[i + j] = right_b[j]; j++; } } return; } void sort_a2(int *a, int *b, int size) { if( size < 2 ) { return; } int m = ( size + 1 ) / 2, i; int *left_a, *left_b, *right_a, *right_b; left_a = (int*)malloc(m * sizeof(int)); right_a = (int*)malloc(( size - m ) * sizeof(int)); left_b = (int*)malloc(m * sizeof(int)); right_b = (int*)malloc(( size - m ) * sizeof(int)); for( i = 0 ; i < m ; i++ ) { left_a[i] = a[i]; left_b[i] = b[i]; } for( i = 0 ; i < size - m ; i++ ) { right_a[i] = a[i + m]; right_b[i] = b[i + m]; } sort_a2(left_a, left_b, m); sort_a2(right_a, right_b, size - m); merge2(a, left_a, right_a, b, left_b, right_b, m, size - m); free(left_a); free(right_a); free(left_b); free(right_b); return; } void merge3(int *a, int *left_a, int *right_a, int *b, int *left_b, int *right_b, int *c, int *left_c, int *right_c, int left_size, int right_size) { int i = 0, j = 0; while( i < left_size || j < right_size ) { if( i == left_size ) { a[i + j] = right_a[j]; b[i + j] = right_b[j]; c[i + j] = right_c[j]; j++; } else if( j == right_size ) { a[i + j] = left_a[i]; b[i + j] = left_b[i]; c[i + j] = left_c[i]; i++; } else if( left_a[i] <= right_a[j] ) { a[i + j] = left_a[i]; b[i + j] = left_b[i]; c[i + j] = left_c[i]; i++; } else { a[i + j] = right_a[j]; b[i + j] = right_b[j]; c[i + j] = right_c[j]; j++; } } return; } void sort_a3(int *a, int *b, int *c, int size) { if( size < 2 ) { return; } int m = ( size + 1 ) / 2, i; int *left_a, *left_b, *left_c, *right_a, *right_b, *right_c; left_a = (int*)malloc(m * sizeof(int)); right_a = (int*)malloc(( size - m ) * sizeof(int)); left_b = (int*)malloc(m * sizeof(int)); right_b = (int*)malloc(( size - m ) * sizeof(int)); left_c = (int*)malloc(m * sizeof(int)); right_c = (int*)malloc(( size - m ) * sizeof(int)); for( i = 0 ; i < m ; i++ ) { left_a[i] = a[i]; left_b[i] = b[i]; left_c[i] = c[i]; } for( i = 0 ; i < size - m ; i++ ) { right_a[i] = a[i + m]; right_b[i] = b[i + m]; right_c[i] = c[i + m]; } sort_a3(left_a, left_b, left_c, m); sort_a3(right_a, right_b, right_c, size - m); merge3(a, left_a, right_a, b, left_b, right_b, c, left_c, right_c, m, size - m); free(left_a); free(right_a); free(left_b); free(right_b); free(left_c); free(right_c); return; } void heap_insert(node *heap, node *elem, int *size, int *heap_list) { (*size)++; int index = (*size); while( index > 1 && elem -> w < heap[index / 2].w ) { heap[index] = heap[index / 2]; heap_list[heap[index].u] = index; index /= 2; } heap[index] = (*elem); heap_list[elem -> u] = index; return; } void heap_update(node *heap, node *elem, int *heap_list) { int index = heap_list[elem -> u]; while( index > 1 && elem -> w < heap[index / 2].w ) { heap[index] = heap[index / 2]; heap_list[heap[index].u] = index; index /= 2; } heap[index] = (*elem); heap_list[elem -> u] = index; return; } void heap_read(node *heap, int *size, int *heap_list, node *ans) { (*ans) = heap[1]; int index = 1; while( index * 2 < *size && heap[*size].w > heap[index * 2].w || index * 2 + 1 < *size && heap[*size].w > heap[index * 2 + 1].w ) { index = ( heap[index * 2].w > heap[index * 2 + 1].w ) ? index * 2 + 1 : index * 2; heap[index / 2] = heap[index]; heap_list[heap[index].u] = index / 2; } heap[index] = heap[*size]; heap_list[heap[index].u] = index; (*size)--; return; } long long med(long long *a, int size) { return a[(size - 1) >> 1]; } int get_i(long long *a, long long num, int size) { if( size == 0 ) { return 0; } if( num >= med(a, size) ) { return get_i(&a[(size + 1) >> 1], num, size >> 1) + ((size + 1) >> 1); } else { return get_i(a, num, (size - 1) >> 1); } } void range_increment(int i, int j, long long val, long long *tree, int N) { for( i += N, j += N ; i <= j ; i = ( i + 1 ) / 2, j = ( j - 1 ) / 2 ) { if( i % 2 && ( tree[i] == -1 || tree[i] > val ) ) { tree[i] = val; } if( j % 2 == 0 && ( tree[j] == -1 || tree[j] > val ) ) { tree[j] = val; } } return; } long long query(int i, long long *tree, int N) { long long ans = -1, j; for( j = i + N ; j ; j /= 2 ) { if( ans == -1 || ans > tree[j] && tree[j] != -1 ) { ans = tree[j]; } } return ans; } void DJ(int N, int M, int *u, int *v, int *w, int *v_right, int *list_index, int *left_index, int *right_index, int S, long long *d, int *bridge, int *island) { int i, next_solve, heap_size = 0, *heap_list, island_num; node elem, *heap; heap = (node*)malloc(N * sizeof(node)); heap_list = (int*)malloc(N * sizeof(int)); d[S] = 0; island[S] = 0; next_solve = S; while(1) { for( i = left_index[next_solve] ; i >= 0 && i < M && u[i] == next_solve ; i++ ) { if( d[v[i]] == -1 || d[v[i]] > d[next_solve] + w[i] ) { elem.u = v[i]; elem.w = d[next_solve] + w[i]; if( d[v[i]] == -1 ) { heap_insert(heap, &elem, &heap_size, heap_list); } else { heap_update(heap, &elem, heap_list); } d[v[i]] = d[next_solve] + w[i]; if( bridge[i] == 2 ) { island[v[i]] = island[next_solve] + 1; } else { island[v[i]] = island[next_solve]; } } else if( d[v[i]] == d[next_solve] + w[i] ) { if( bridge[i] == 2 ) { island_num = island[next_solve] + 1; } else { island_num = island[next_solve]; } if( island[v[i]] > island_num ) { island[v[i]] = island_num; } } } for( i = right_index[next_solve] ; i >= 0 && i < M && v_right[i] == next_solve ; i++ ) { if( d[u[list_index[i]]] == -1 || d[u[list_index[i]]] > d[next_solve] + w[list_index[i]] ) { elem.u = u[list_index[i]]; elem.w = d[next_solve] + w[list_index[i]]; if( d[u[list_index[i]]] == -1 ) { heap_insert(heap, &elem, &heap_size, heap_list); } else { heap_update(heap, &elem, heap_list); } d[u[list_index[i]]] = d[next_solve] + w[list_index[i]]; if( bridge[list_index[i]] == 2 ) { island[u[list_index[i]]] = island[next_solve] + 1; } else { island[u[list_index[i]]] = island[next_solve]; } } else if( d[u[list_index[i]]] == d[next_solve] + w[list_index[i]] ) { if( bridge[list_index[i]] == 2 ) { island_num = island[next_solve] + 1; } else { island_num = island[next_solve]; } if( island[u[list_index[i]]] > island_num ) { island[u[list_index[i]]] = island_num; } } } if( heap_size == 0 ) { break; } heap_read(heap, &heap_size, heap_list, &elem); next_solve = elem.u; } free(heap); free(heap_list); return; } int main() { int N, M, S, D, Q, x, y, p, f, b, i, j; int *u, *v, *w, *v_right, *list_index, *left_index, *right_index, *bridge, *island; long long *d_s, *d_d, *path, *bypass; scanf("%d%d", &N, &M); u = (int*)malloc(M * sizeof(int)); v = (int*)malloc(M * sizeof(int)); w = (int*)malloc(M * sizeof(int)); v_right = (int*)malloc(M * sizeof(int)); list_index = (int*)malloc(M * sizeof(int)); left_index = (int*)malloc(M * sizeof(int)); right_index = (int*)malloc(M * sizeof(int)); d_s = (long long*)malloc(N * sizeof(long long)); d_d = (long long*)malloc(N * sizeof(long long)); bridge = (int*)malloc(M * sizeof(int)); path = (long long*)malloc(M * sizeof(long long)); island = (int*)malloc(N * sizeof(int)); bypass = (long long*)malloc(M * 3 * sizeof(long long)); for( i = 0 ; i < M ; i++ ) { scanf("%d%d%d", u + i, v + i, w + i); list_index[i] = i; bridge[i] = 0; } for( i = 0 ; i < N ; i++ ) { d_s[i] = d_d[i] = -1; } for( i = 0 ; i < M * 3 ; i++ ) { bypass[i] = -1; } sort_a3(u, v, w, M); for( i = 0 ; i < M ; i++ ) { v_right[i] = v[i]; } sort_a2(v_right, list_index, M); for( i = 0 ; i < M ; i++ ) { if( i == 0 || u[i] != u[i - 1] ) { left_index[u[i]] = i; } if( i == 0 || v_right[i] != v_right[i - 1] ) { right_index[v_right[i]] = i; } } scanf("%d%d%d", &S, &D, &Q); f = 0; DJ(N, M, u, v, w, v_right, list_index, left_index, right_index, S, d_s, bridge, island); DJ(N, M, u, v, w, v_right, list_index, left_index, right_index, D, d_d, bridge, island); if( d_s[D] == -1 ) { f = 1; } else { for( i = 0, p = 0 ; i < M ; i++ ) { if( d_s[u[i]] != -1 && ( d_s[u[i]] + d_d[v[i]] + w[i] == d_s[D] || d_s[v[i]] + d_d[u[i]] + w[i] == d_s[D] ) ) { bridge[i] = 1; path[p] = ( d_s[u[i]] > d_s[v[i]] ) ? d_s[u[i]] : d_s[v[i]]; p++; } } sort_a(path, p); for( i = 0, b = 0 ; i < M ; i++ ) { if(bridge[i]) { x = ( d_s[u[i]] < d_s[v[i]] ) ? d_s[u[i]] : d_s[v[i]]; y = ( d_s[u[i]] < d_s[v[i]] ) ? d_s[v[i]] : d_s[u[i]]; j = get_i(path, x, p); if( path[j] == y && ( j == p - 1 || path[j + 1] > y ) ) { bridge[i] = 2; b++; } } } for( i = 0 ; i < N ; i++ ) { d_s[i] = island[i] = -1; } DJ(N, M, u, v, w, v_right, list_index, left_index, right_index, S, d_s, bridge, island); for( i = 0 ; i < M ; i++ ) { if( bridge[i] != 2 ) { x = ( island[u[i]] > island[v[i]] ) ? island[v[i]] : island[u[i]]; y = ( island[u[i]] > island[v[i]] ) ? island[u[i]] : island[v[i]]; j = ( island[u[i]] > island[v[i]] ) ? d_s[v[i]] + w[i] + d_d[u[i]] : d_s[u[i]] + w[i] + d_d[v[i]]; range_increment(x + 1, y, j, bypass, b); } } } while(Q--) { scanf("%d%d", &x, &y); if(f) { printf("Infinity\n"); } else { for( i = left_index[x] ; i >= 0 && i < M && u[i] == x ; i++ ) { if( v[i] == y ) { if( bridge[i] == 2 ) { if( query(( island[u[i]] > island[v[i]] ) ? island[v[i]] + 1 : island[u[i]] + 1, bypass, b) == -1 ) { printf("Infinity\n"); } else { printf("%lld\n", query(( island[u[i]] > island[v[i]] ) ? island[v[i]] + 1 : island[u[i]] + 1, bypass, b)); } } else { printf("%lld\n", d_s[D]); } } } for( i = right_index[x] ; i >= 0 && i < M && v_right[i] == x ; i++ ) { if( u[list_index[i]] == y ) { if( bridge[list_index[i]] == 2 ) { if( query(( island[u[list_index[i]]] > island[v[list_index[i]]] ) ? island[v[list_index[i]]] + 1 : island[u[list_index[i]]] + 1, bypass, b) == -1 ) { printf("Infinity\n"); } else { printf("%lld\n", query(( island[u[list_index[i]]] > island[v[list_index[i]]] ) ? island[v[list_index[i]]] + 1 : island[u[list_index[i]]] + 1, bypass, b)); } } else { printf("%lld\n", d_s[D]); } } } } } return 0; } Going to the Office C++ Solution #include <cstdlib> #include <cctype> #include <cstring> #include <cstdio> #include <cmath> #include <algorithm> #include <vector> #include <string> #include <iostream> #include <sstream> #include <map> #include <set> #include <queue> #include <stack> #include <fstream> #include <numeric> #include <iomanip> #include <bitset> #include <list> #include <stdexcept> #include <functional> #include <utility> #include <ctime> #include <complex> using namespace std; // begin insert defines #define PR pair template<typename S, typename T> ostream& operator<<(ostream& os, pair<S,T> p){ return os << "(" << p.first << "," << p.second << ")"; }; template <class T> void PV(T x) {for(__typeof__((x).begin()) i = (x).begin(); i != (x).end(); i++) cout << *i << " "; cout << endl;} template <class T> void PA(T x[], int n) {for (int i = 0; i < n; i++) cout << x[i] << " "; cout << endl;} #define MP make_pair #define forE(elem,v) for(__typeof__(v.begin()) _it = v.begin(); _it != v.end();++_it) for(int _once=1, _done=0; _once; (!_done) ? (_it=v.end(), --_it) :_it ) for(__typeof__(*_it) & elem = * _it; _once && !(_once=0); _done=1) typedef vector<int> VRI; typedef pair<int, int> PII; #define Rep(i,n) for(int n_ = (n), i = 0; i< n_; ++i) typedef long long ll; // end insert defines const int N = 200010, M = 200010; const ll INF = 1000000000000000000LL; struct Lnk { int v, next; ll w; }lnk[M * 2]; int st[N], lnn; inline void ae(int u, int v, ll w) { lnk[lnn].v = v; lnk[lnn].w = w; lnk[lnn].next = st[u]; st[u] = lnn++; } map<PII, ll> ans; int n, m, bgn, mend, qn; ll d[2][N], pre[N]; int q[N]; bool in[N]; VRI son[N]; void bfs(int bgn, int end, ll d[N]) { int f = 0, r = 1; q[f] = bgn; memset(in, 0, sizeof(in)); in[bgn] = true; fill(d, d + n, INF); d[bgn] = 0; pre[bgn] = -1; for (; f < r; f++) { int now = q[f]; for (int i = st[now]; i != -1; i = lnk[i].next) { int v = lnk[i].v; if (d[now] + lnk[i].w < d[v]) { d[v] = d[now] + lnk[i].w; pre[v] = now; if (!in[v]) { in[v] = true; q[r++] = v; } } } in[now] = false; } } bool vis[N]; struct T { ll val; int u, v; friend bool operator < (const T &l, const T &r) { if (l.val != r.val) return l.val < r.val; if (l.u != r.u) return l.u < r.u; return l.v < r.v; } void as(int _u, int _v, ll _val) { if (_u > _v) swap(_u, _v); u = _u, v = _v, val = _val; } }; int f, r; set<T> can; void bfs2(int bgn) { f = 0, r = 1; q[f] = bgn; vis[bgn] = true; for (; f < r; f++) { int now = q[f]; forE(v, son[now]) { if (!vis[v]) { vis[v] = true; q[r++] = v; } } } } void solve() { struct T t; memset(vis, 0, sizeof(vis)); Rep(i, n) if (pre[i] != -1) son[pre[i]].push_back(i); can.clear(); for (int p = mend; p != bgn; p = pre[p]) { bfs2(p); Rep(j, r) { int now = q[j]; for (int k = st[now]; k != -1; k = lnk[k].next) { int v = lnk[k].v; if (now == p && v == pre[p]) continue; ll w = lnk[k].w; if (vis[v]) { t.as(now, v, d[0][now] + d[1][v] + w); can.erase(t); } else { t.as(now, v, d[0][v] + d[1][now] + w); can.insert(t); } } } if (can.empty()) ans[MP(pre[p], p)] = ans[MP(p, pre[p])] = INF; else ans[MP(pre[p], p)] = ans[MP(p, pre[p])] = can.begin()->val; } } int main(int argc, char *argv[]) { scanf("%d%d", &n, &m); lnn = 0; memset(st, -1, sizeof(st)); ans.clear(); Rep(i, m) { int u, v; ll w; scanf("%d%d%lld", &u, &v, &w); ae(u, v, w); ae(v, u, w); } scanf("%d%d", &bgn, &mend); bfs(mend, bgn, d[1]); bfs(bgn, mend, d[0]); if (d[0][mend] == INF) { scanf("%d", &qn); Rep(qi, qn) { int u, v; scanf("%d%d", &u, &v); puts("Infinity"); } } else { solve(); scanf("%d", &qn); Rep(qi, qn) { int u, v; scanf("%d%d", &u, &v); ll a; if (ans.count(MP(u, v))) a = ans[MP(u, v)]; else a = d[0][mend]; if (a == INF) puts("Infinity"); else printf("%lld\n", a); } } return 0; } Going to the Office C Sharp Solution using System; using System.Collections.Generic; using System.IO; using System.Text; using System.Linq; using TestHackerRank; class Solution { public class Reader { public Reader(string file = null) { // In Visual Studio, there are three bytes before the actual text // in the file that you redirect. if (null == file) { _reader = Console.In; #if VS Console.Read(); Console.Read(); Console.Read(); #endif } else { _reader = File.OpenText(file); } } public string ReadLine() { return _reader.ReadLine(); } TextReader _reader; } static void Main(String[] argsx) { #if VS var reader = new Reader(@"C:\Users\250894\Documents\Visual Studio 2015\Projects\TestHackerRank\TestInput2-1.txt"); #else var reader = new Reader(); #endif string[] args = reader.ReadLine().Split(' '); int nCities = Convert.ToInt32(args[0]); int nRoutes = Convert.ToInt32(args[1]); var adjMatrix = (from x in new int[nCities] select new Dictionary<int, int>()).ToArray(); for (int i = 0; i < nRoutes; i++) { var edge = (from s in reader.ReadLine().Split(' ') select Convert.ToInt32(s)).ToArray(); int c1 = edge[0]; int c2 = edge[1]; int dist = edge[2]; // This is an undirected graph, so we'll populate it in both // directions. adjMatrix[c1][c2] = adjMatrix[c2][c1] = dist; } args = reader.ReadLine().Split(' '); int orig = Convert.ToInt32(args[0]); int dest = Convert.ToInt32(args[1]); int q = Convert.ToInt32(reader.ReadLine()); var solver = new Dijsktra(adjMatrix, orig, dest); for (int i = 0; i < q; i++) { args = reader.ReadLine().Split(' '); int c1 = Convert.ToInt32(args[0]); int c2 = Convert.ToInt32(args[1]); int dist = solver.Reroute(c1, c2); Console.WriteLine(dist != int.MaxValue ? dist.ToString() : "Infinity"); } } } namespace TestHackerRank { public class Node : IComparable { public Node(int id, IList<Node> nodes) { Id = id; Dist = int.MaxValue; Previous = -1; Nodes = nodes; Island = -1; } public int CompareTo(object other) { int retVal = 1; if (null != other && other is Node) { retVal = Dist.CompareTo(((Node)other).Dist); } else { throw new ArgumentException("Object is not a DistNode"); } return retVal; } public int Id { get; set; } public int Dist { get; set; } public IList<Node> Nodes { get; private set; } public int Island { get; set; } public int Previous { get; set; } private List<int> _neighbors; public List<int> Neighbors { get { if (null == _neighbors) { _neighbors = new List<int>(); } return _neighbors; } set { _neighbors = value; } } public IList<int> Path { get { List<int> retVal = new List<int>(); var current = this; while(current.Dist != 0 && current.Dist != -1 && current.Dist != int.MaxValue) { retVal.Add(current.Id); current = Nodes[current.Previous]; } return retVal; } } public override int GetHashCode() { return Id.GetHashCode(); } public override string ToString() { StringBuilder sb = new StringBuilder(string.Format("Id: {0}", Id)); if (int.MaxValue != Dist) { sb.AppendFormat(", Dist: {0}", Dist); } if (-1 != Previous) { sb.AppendFormat(", Previous: {0}", Previous); } if (null != _neighbors && 0 != _neighbors.Count) { sb.AppendFormat(", Neighbor Count: {0}", _neighbors.Count); } if(-1 != Island) { sb.AppendFormat(", Island: {0}", Island); } return sb.ToString(); } public override bool Equals(object obj) { bool ret = false; if (null != obj && obj is Node) { ret = ((Node)obj).Id == Id; } return ret; } } public class Edge : IComparable { public Edge(int v1, int v2, int dist, int fromOrigin, int fromDest) { V1 = v1; V2 = v2; Distance = dist; dsU = fromOrigin; dtV = fromDest; Bridge = false; Iu = Iv = -1; } public static bool IsForward(int node, int neighbor, IList<Node> nodes) { return nodes[node].Dist < nodes[neighbor].Dist; } /// <summary> /// True if this is a bridge. /// </summary> public bool Bridge { get; set; } /// <summary> /// Vertex 1. /// </summary> public int V1 { get; private set; } /// <summary> /// Vertex 2. /// </summary> public int V2 { get; private set; } /// <summary> /// Cost for traversing this edge. /// </summary> public int Distance { get; private set; } /// <summary> /// Distance from the beginning of this edge to the start vertex. /// </summary> public int dsU { get; private set; } /// <summary> /// Distance from the end of this edge to the end vertex. /// </summary> public int dtV { get; private set; } /// <summary> /// Index to this edge in the collection sorted by distance from beginning point to the beginning of this edge (dsU). /// </summary> public int Iu { get; set; } /// <summary> /// Index to this edge in the collection sorted by distance from beginning point to the end of this edge (dsV). /// </summary> public int Iv { get; set; } /// <summary> /// Distance from end of this edge to the beginning point (calculated). /// </summary> public int dtU { get { return dtV + Distance; } } /// <summary> /// Distance from the beginning of this edge to the end point (calculated). /// </summary> public int dsV { get { return dsU + Distance; } } public int TotalDistance { get { return dsU + Distance + dtV; } } public override string ToString() { string retVal = string.Format("{0} <==> {1}, Weight: {2}, dsU: {3}, dsV: {4}, dtV: {5}", V1, V2, Distance, dsU, dsV, dtV); if (Bridge) { // This is not the best form, but ToString is only used here // when debugging. retVal += " Bridge"; } return retVal; } public override bool Equals(object obj) { bool fRet = false; if(null != obj && obj is Edge) { Edge other = (Edge)obj; fRet = other.V1 == V1 && other.V2 == V2 && other.Distance == Distance && other.dsU == dsU && other.dtV == dtV; } return fRet; } public override int GetHashCode() { return (V1 + V2 + Distance + dsU + dtV).GetHashCode(); } #region IComparable int IComparable.CompareTo(object obj) { // We want to sort by dsU, reverse dsV, V1, and V2. If there is a // case where all of these are equal, then something's wrong with // the data. int iRet = -1; if(null != obj && obj is Edge) { var other = (Edge)obj; if(0 == (iRet = other.dsU.CompareTo(dsU)) || 0 == (iRet = -(other.dsV.CompareTo(dsV))) || 0 == (iRet = other.V1.CompareTo(V1))) { iRet = other.V2.CompareTo(V2); } } return iRet; } #endregion #region IComparers public class BydsU : IComparer<Edge> { public int Compare(Edge x, Edge y) { var ret = x.dsU.CompareTo(y.dsU); if(0 == ret) { ret = - x.dsV.CompareTo(y.dsV); } if(0 == ret) { ret = x.V1.CompareTo(y.V1); } if(0 == ret) { ret = x.V2.CompareTo(y.V2); } return ret; } } public class BydsV : IComparer<Edge> { public int Compare(Edge x, Edge y) { var ret = x.dsV.CompareTo(y.dsV); if(0 == ret) { ret = x.dsU.CompareTo(y.dsU); } if (0 == ret) { ret = x.V1.CompareTo(y.V1); } if (0 == ret) { ret = x.V2.CompareTo(y.V2); } return ret; } } #endregion } public class Dijsktra { public Dijsktra(IList<Dictionary<int, int>> paths, int src, int dest) { _paths = paths; _src = src; _dest = dest; // Create the forward and reverse arrays. _forwardNodes = CreateNodeArray(paths); _reverseNodes = CreateNodeArray(paths); _edgeDict = new Dictionary<Tuple<int, int>, Edge>(); Solve(); } private static Node[] CreateNodeArray(IList<Dictionary<int, int>> paths) { // Create the nodes. var retVal = new Node[paths.Count]; for(int i = 0; i < paths.Count; i++) { retVal[i] = new Node(i, retVal); } // Set up the adjacency. for (int i = 0; i < paths.Count; i++) { foreach (var path in paths[i]) { retVal[i].Neighbors.Add(path.Key); } } return retVal; } private IList<Dictionary<int, int>> _paths; private Node[] _forwardNodes; private Node[] _reverseNodes; private HashSet<Node> _settled; private MinHeap<Node> _unsettled; private SortedSet<Edge> _optimalEdges; private Dictionary<Tuple<int, int>, Edge> _edgeDict; private List<Edge> _optimalByV; private List<Edge> _optimalByU; private int _src = -1; private int _dest = -1; private int _optimalDistance = -1; List<int> _bypasses; public void SortByDist(ref int v1, ref int v2) { // We're going to sort by distance. // If dtV is the same, then dsU. If they're the same, then index number. int n1, n2; int dtV1 = _reverseNodes[v1].Dist; int dtV2 = _reverseNodes[v2].Dist; int dsU1 = _forwardNodes[v1].Dist; int dsU2 = _forwardNodes[v2].Dist; if(dtV1 != dtV2) { n1 = dtV1 > dtV2 ? v1 : v2; n2 = dtV2 < dtV1 ? v2 : v1; } else if(dsU1 != dsU2) { n1 = dsU1 < dsU2 ? v1 : v2; n2 = dsU2 > dsU1 ? v2 : v1; } else { n1 = v1 < v2 ? v1 : v2; n2 = v2 > v1 ? v2 : v1; } v1 = n1; v2 = n2; } public int Reroute(int closed1, int closed2) { SortByDist(ref closed1, ref closed2); var edgeId = new Tuple<int, int>(closed1, closed2); int retVal = _optimalDistance; Edge edge = null; if(_edgeDict.TryGetValue(edgeId, out edge) && edge.Bridge) { // We're getting the higher island number. // Maybe later we'll just use the node that's further, since it // should logically have the higher island number. int bn = Math.Max(_forwardNodes[closed1].Island, _forwardNodes[closed2].Island) - 1; retVal = _bypasses[bn]; } #if DEBUG_REROUTE var save = _paths[closed1][closed2]; _paths[closed1].Remove(closed2); _paths[closed2].Remove(closed1); var nodes = CreateNodeArray(_paths); int dist = RunDijsktra(nodes, _src, _dest); _paths[closed1][closed2] = _paths[closed2][closed1] = save; System.Diagnostics.Debug.Assert(dist == retVal); #endif return retVal; } private int RunDijsktra(IList<Node> nodes, int first, int last) { _settled = new HashSet<Node>(); _unsettled = new MinHeap<Node>(); nodes[first].Dist = 0; _unsettled.Add(nodes[first]); while(0 != _unsettled.Count) { var node = _unsettled.PopMin(); _settled.Add(node); foreach (var iAdjNode in node.Neighbors) { var adjNode = nodes[iAdjNode]; if (!_settled.Contains(adjNode) && int.MaxValue != node.Dist && adjNode.Dist > node.Dist + _paths[node.Id][adjNode.Id]) { adjNode.Dist = node.Dist + _paths[node.Id][adjNode.Id]; adjNode.Previous = node.Id; _unsettled.Add(adjNode); } } } return nodes[last].Dist; } private int RunDijsktra() { // First, calculate the forward path. int retVal = RunDijsktra(_forwardNodes, _src, _dest); // Next, calculate the reverse path. RunDijsktra(_reverseNodes, _dest, _src); return retVal; } public bool IsBridge(Edge e) { bool fRet = false; int iu = e.Iu; int iv = e.Iv; Edge ep; // First of all, e.V is always > e.U. So, if we start with e.Iv, // it's going to point to an edge where V > e.U. // * For now, I'm going on the assumption that the cost will always // be greater than zero. If we have paths where the cost is zero, // it will cause this algorithm to be more complicated. I'm not // even sure Dijkstra's algorithm will handle zero-cost. It // definitely requires changes to handle negative. ep = e; // The next step is to move backwards to see if e is the first // edge that meets that condition. while (ep.dsV > e.dsU) { if (--iv < 0) { iv = 0; break; } ep = _optimalByV[iv]; } // Now, these are the possibilities (and sub-possibilities). // * We're pointing to an edge with a V <= e.U. // * We're pointing to e // * It's the first edge in the list. // * It's the only edge in the list. // * We're pointing to the first edge in the list, and V > e.U. // The first one's the easiest. We just need to move forward one. if (ep.dsV <= e.dsU) { // Let's point to the next one, which will satisfy V > e.U. ep = _optimalByV[++iv]; } // Next, the cases where ep == e. if (iv == e.Iv) // This is a lot faster than Equals. { // Is e the last edge in the list? If so, then it's definitely // a bridge since there can't be any edges where V > e.U. if (iv == _optimalByV.Count - 1) { fRet = true; } // Otherwise, we just need to move forward one. else { ep = _optimalByV[++iv]; } } // If we're pointing to the first edge in the list, and V > e.U, // then we're already where we need to be. // Now, we're either pointing to an edge that isn't e whose V > e.U // or this is a bridge. // If we haven't already definitely confirmed bridge status, let's // find the first edge with a U that's less than e.V. if (!fRet) { // Once again, we'll start with e because e.U will always be < e.V. ep = e; // Move forward to the first U that's >= e.V. while (ep.dsU < e.dsV) { if (++iu >= _optimalByU.Count) { iu--; break; } ep = _optimalByV[iu]; } // Once again, we have to handle the different possibilities and // sub-possibilities. // * We're pointing to an edge where U >= e.V. // * We're pointing to e. // * It's the last edge in the list. // * It's the first edge in the list. // * We're pointing to the last edge in the list, and U < e.V. // Again, the first case is simple. if (ep.dsU >= e.dsV) { // Let's point to the previous one, which will satisfy // U < e.V. ep = _optimalByU[--iu]; } // Next, the cases where ep == e. if (iu == e.Iu) // This is a lot faster than Equals. { // Is e the first edge in the list? If so, then it's definitely // a bridge since there can't be any edges where U < e.V. if (iu == 0) { fRet = true; } // Otherwise, we just need to back up by one. else { ep = _optimalByU[--iu]; } } } if(!fRet) { // If we're here, then we have an index to the first V > e.U // and the first U < e.V. We need to see if they intersect. // We'll start with the first V that's > e.U. var firstV = _optimalByV[iv]; if(firstV.Iu > iu) { fRet = true; } } return fRet; } public int Solve() { _optimalDistance = RunDijsktra(); if (-1 != _optimalDistance) { #region Find the optimal edges. _optimalEdges = new SortedSet<Edge>(new Edge.BydsU()); for (int node = 0; node < _forwardNodes.Length; node++) { foreach (int neighbor in _forwardNodes[node].Neighbors) { // We're going to sort by distance from source so that we're always // moving towards the destination. int v1 = node; int v2 = neighbor; SortByDist(ref v1, ref v2); var edgeId = new Tuple<int, int>(v1, v2); if (!_edgeDict.ContainsKey(edgeId) && v1 != v2 // Not possible with good data. ) { var toStart = _forwardNodes[v1].Dist; var toEnd = _reverseNodes[v2].Dist; var edgeDist = _paths[v1][v2]; var edge = new Edge(v1, v2, edgeDist, toStart, toEnd); _edgeDict[edgeId] = edge; // Test for optimal edge. if (toStart + edgeDist + toEnd == _optimalDistance) { if (!_optimalEdges.Contains(edge)) { _optimalEdges.Add(edge); } } } } } #endregion #region Prepare sorted lists // We need a list sorted by dsU. _optimalEdges already is, but // we need it in a form that can be quickly accessed by index. _optimalByU = new List<Edge>(_optimalEdges.Count); int ie = 0; foreach (var edge in _optimalEdges) { edge.Iu = ie++; _optimalByU.Add(edge); } // We also need a list sorted by dsV. _optimalByV = new List<Edge>(_optimalEdges.Count); var sorted = _optimalEdges.OrderBy(ep => ep.dsV); ie = 0; foreach (var edge in sorted) { edge.Iv = ie++; _optimalByV.Add(edge); } #endregion #region Find Bridges var bridges = new SortedSet<Edge>(new Edge.BydsV()); // Now, we'll go through the list sorted by dsU. for (ie = 0; ie < _optimalEdges.Count; ie++) { var e = _optimalByU[ie]; if(IsBridge(e)) { e.Bridge = true; bridges.Add(e); } } #endregion #region Find Islands Queue<Node> nodeQueue = new Queue<Node>(); nodeQueue.Enqueue(_forwardNodes[_src]); _forwardNodes[_src].Island = 0; while(nodeQueue.Count > 0) { var node = nodeQueue.Dequeue(); foreach (var neighbor in node.Neighbors) { var next = _forwardNodes[neighbor]; if (Edge.IsForward(node.Id, neighbor, _forwardNodes)) { int v1 = node.Id, v2 = neighbor; SortByDist(ref v1, ref v2); var edgeId = new Tuple<int, int>(v1, v2); var island = _edgeDict.ContainsKey(edgeId) && _edgeDict[edgeId].Bridge ? Math.Max(node.Island + 1, next.Island) : Math.Max(node.Island, next.Island); if (next.Island != island) { next.Island = island; nodeQueue.Enqueue(next); } } } } #endregion // We'll create a collection of edge identifiers representing // the bridges. Then, we'll go through all of the non-bridge // edges that span islands. For every island in between, we'll // check dsU + Distance + dtV, and if it's less than what's // there, we'll update it. When we're done, we'll have a lookup // of bypass values. _bypasses = (from item in new int[bridges.Count] select int.MaxValue).ToList(); foreach(var edge in _edgeDict.Values) { // If it's not a bridge and it does span multiple islands. if(!edge.Bridge && _forwardNodes[edge.V1].Island != _forwardNodes[edge.V2].Island) { // It matters which one is closer to which end. int v1 = edge.V1, v2 = edge.V2; SortByDist(ref v1, ref v2); var first = _forwardNodes[v1].Island; var second = _forwardNodes[v2].Island; for(int i = first; i < second; i++) { _bypasses[i] = Math.Min(_bypasses[i], edge.TotalDistance); } } } } return _optimalDistance; } } class MinHeap<T> where T : IComparable { public MinHeap(int cap = -1) { if (cap <= 0) { _items = new List<T>(); } else { _items = new List<T>(cap); } } public MinHeap(IList<T> items) { _items = items; Reorder(); } public void Reorder() { int heapSize = _items.Count - 1; for (int i = heapSize / 2; i >= 0; i--) { SiftDown(i); } } public int Count { get { return _items.Count; } } void SiftUp(int index, int exclusion = 0) { if(0 != index) { int parent = (index - 1) / 2; if(_items[parent].CompareTo(_items[index]) > 0) { T swap = _items[parent]; _items[parent] = _items[index]; _items[index] = swap; SiftUp(parent); } } } void SiftDown(int index, int exclusion = 0) { int heapLen = _items.Count - exclusion; int left = (2 * index + 1); int right = left + 1; int min = index; if (left < heapLen && _items[left].CompareTo(_items[min]) < 0) { min = left; } if (right < heapLen && _items[right].CompareTo(_items[min]) < 0) { min = right; } if (index != min) { T swap = _items[index]; _items[index] = _items[min]; _items[min] = swap; SiftDown(min, exclusion); } } public void Add(T item) { _items.Add(item); if (_items.Count > 1) { SiftUp(_items.Count - 1); } } public T PopMin() { T top = _items[0]; _items[0] = _items[_items.Count - 1]; Items.RemoveAt(_items.Count - 1); if (_items.Count > 1) { SiftDown(0); } return top; } public T PeekMin() { return _items[0]; } public IList<T> Items { get { return _items; } } static void Sort<I>(IList<I> items) where I : IComparable { var heap = new MinHeap<I>(items); int sortedLen = 0; for(int i = items.Count - 1; i >= 0; i--) { I swap = items[0]; items[0] = items[i]; items[i] = swap; sortedLen++; heap.SiftDown(0, sortedLen); } } #region Private Fields private IList<T> _items; #endregion } } Going to the Office Java Solution import java.io.*; import java.util.*; public class Solution { static class Edge { int v; long w; public Edge(int v, long w) { this.v = v; this.w = w; } } static class Node implements Comparable<Node> { long d; int v; public Node(long d, int v) { this.d = d; this.v = v; } @Override public int compareTo(Node o) { if (d == o.d) return 0; return d > o.d ? 1 : -1; } } static int[] nxt; static Edge[] succ; static int[] ptr; static int index = 1; static void add(int u, int v, long w) { nxt[index] = ptr[u]; ptr[u] = index; succ[index++] = new Edge(v, w); nxt[index] = ptr[v]; ptr[v] = index; succ[index++] = new Edge(u, w); } static int time = 0; static int[] disc; static int[] low; static boolean[] vis; static long[] dis; static int[] parent; static class NodeDfs { int u; int p; boolean start = true; public NodeDfs(int u, int p) { this.u = u; this.p = p; } } static class HEdge { int u; int v; public HEdge(int u, int v) { if (u > v) { int tmp = u; u = v; v = tmp; } this.u = u; this.v = v; } @Override public int hashCode() { final int prime = 31; int result = 1; result = prime * result + u; result = prime * result + v; return result; } @Override public boolean equals(Object obj) { if (this == obj) return true; if (obj == null) return false; if (getClass() != obj.getClass()) return false; HEdge other = (HEdge) obj; if (u != other.u) return false; if (v != other.v) return false; return true; } } static Set<HEdge> bridges = new HashSet<>(); static void bridgeDfs(int s) { Deque<NodeDfs> queue = new LinkedList<>(); queue.add(new NodeDfs(s, -1)); while (!queue.isEmpty()) { NodeDfs node = queue.peekLast(); if (node.start) { if (!vis[node.u]) { vis[node.u] = true; disc[node.u] = low[node.u] = ++time; for (int i = ptr[node.u]; i > 0; i = nxt[i]) { parent[succ[i].v] = node.u; queue.add(new NodeDfs(succ[i].v, node.u)); } node.start = false; } else { if (node.u != parent[node.p]) { low[node.p] = Math.min(low[node.p], disc[node.u]); } queue.removeLast(); } } else { if (node.p >= 0) { low[node.p] = Math.min(low[node.p], low[node.u]); if (low[node.u] > disc[node.p]) { bridges.add(new HEdge(node.p, node.u)); } } queue.removeLast(); } } } static void dijkstra1(int src) { dis[src] = 0; PriorityQueue<Node> queue = new PriorityQueue<>(); queue.add(new Node(0, src)); while (!queue.isEmpty()) { Node x = queue.poll(); if (vis[x.v]) { continue; } vis[x.v] = true; for (int i = ptr[x.v]; i > 0; i = nxt[i]) { Edge e = succ[i]; if (x.d + e.w < dis[e.v]) { queue.add(new Node(dis[e.v] = x.d + e.w, e.v)); parent[e.v] = x.v; } } } } static long dijkstra2(int src, int des, int uBlocked, int vBlocked) { dis[src] = 0; PriorityQueue<Node> queue = new PriorityQueue<>(); queue.add(new Node(0, src)); while (!queue.isEmpty()) { Node node = queue.poll(); if (vis[node.v]) { continue; } vis[node.v] = true; for (int i = ptr[node.v]; i > 0; i = nxt[i]) { Edge e = succ[i]; if ((node.v == uBlocked && e.v == vBlocked) || (node.v == vBlocked && e.v == uBlocked)) { continue; } if (node.d + e.w < dis[e.v]) { queue.add(new Node(dis[e.v] = node.d + e.w, e.v)); } } if (node.v == des) { return dis[des]; } } return -1; } public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH"))); StringTokenizer st = new StringTokenizer(br.readLine()); int n = Integer.parseInt(st.nextToken()); int m = Integer.parseInt(st.nextToken()); ptr = new int[n]; parent = new int[n]; nxt = new int[2 * m + 1]; succ = new Edge[2 * m + 1]; for (int i = 0; i < m; i++) { st = new StringTokenizer(br.readLine()); int u = Integer.parseInt(st.nextToken()); int v = Integer.parseInt(st.nextToken()); int w = Integer.parseInt(st.nextToken()); add(u, v, w); } st = new StringTokenizer(br.readLine()); int s = Integer.parseInt(st.nextToken()); int d = Integer.parseInt(st.nextToken()); vis = new boolean[n]; disc = new int[n]; low = new int[n]; bridgeDfs(s); dis = new long[n]; Arrays.fill(dis, Long.MAX_VALUE / 3); Arrays.fill(vis, false); dijkstra1(s); boolean[] b = new boolean[n]; b[d] = true; b[s] = true; int p = d; while ((p = parent[p]) != s) { b[p] = true; } st = new StringTokenizer(br.readLine()); int q = Integer.parseInt(st.nextToken()); long nope = dis[d]; for (int i = 0; i < q; i++) { st = new StringTokenizer(br.readLine()); int u = Integer.parseInt(st.nextToken()); int v = Integer.parseInt(st.nextToken()); long result = nope; if ((parent[u] == v || parent[v] == u) && b[u] && b[v]) { if (bridges.contains(new HEdge(u, v))) { result = -1; } else { Arrays.fill(dis, Long.MAX_VALUE / 3); Arrays.fill(vis, false); result = dijkstra2(s, d, u, v); } } if (result >= 0) { bw.write(result + "\n"); } else { bw.write("Infinity\n"); } } bw.newLine(); br.close(); bw.close(); } } Going to the Office Python Solution import math import copy from heapq import heappush, heappop cities, roads = map(int, input().split()) graph = {n: [] for n in range(cities)} edges = [] for road in range(roads): fr, to, dist = map(int, input().strip().split()) edges.append((fr, to, dist)) graph[fr].append((to, dist)) graph[to].append((fr, dist)) graph_copy = copy.deepcopy(graph) start, finish = map(int, input().strip().split()) number_of_queries = int(input().strip()) queries = [] for q in range(number_of_queries): queries.append(tuple(map(int, input().strip().split()))) def min_path_length(g, s, f): city_list = [{'visited': False, 'dist': math.inf} for c in range(cities)] pq = [] heappush(pq, (0, s)) city_list[s]['dist'] = 0 while pq: current_dist, current_city = heappop(pq) if city_list[current_city]['visited']: continue city_list[current_city]['visited'] = True # if current_city == f: # break for neighbor in g[current_city]: if not city_list[neighbor[0]]['visited']: old_dist = city_list[neighbor[0]]['dist'] new_dist = current_dist + neighbor[1] if new_dist < old_dist: heappush(pq, (new_dist, neighbor[0])) # pq.sort() city_list[neighbor[0]]['dist'] = new_dist return [x['dist'] for x in city_list] def optimal_edges(edges, ds, dt, opt): result = {} for edge in edges: u, v, dist = edge if ds[u] + dist + dt[v] == opt: result[(u, v)] = dist if ds[v] + dist + dt[u] == opt: result[(v, u)] = dist return result def bridges(opt_edges, ds, opt): result = {} sorted_nodes = sorted([((ds[u], ds[v]), (u, v)) for u, v in opt_edges.keys()]) sorted_nodes = [((0, 0), (start, start)), *sorted_nodes, ((opt, opt), (finish, finish))] for i in range(1,len(sorted_nodes) - 1): if sorted_nodes[i][0][0] >= sorted_nodes[i-1][0][1] and sorted_nodes[i][0][1] <= sorted_nodes[i + 1][0][0]: result[sorted_nodes[i][1]] = opt_edges[sorted_nodes[i][1]] return result def arrowed_graph(edges, ds): a_graph = {n: [] for n in range(cities)} for (u, v, dist) in edges: if ds[u] + dist == ds[v]: a_graph[u].append(v) if ds[v] + dist == ds[u]: a_graph[v].append(u) return a_graph def islands(ag, bridges): isl = [0] * cities sorted_bridges = sorted([((ds[u], ds[v]), (u, v)) for u, v in bridges.keys()],) sorted_bridges_ends = [v for ((dsu, dsv),(u, v)) in sorted_bridges] def dfs(fr, ag, island_id): stack = [] stack.append(fr) while stack: current_node = stack.pop() isl[current_node] = island_id for node in ag[current_node]: if isl[node] == 0: stack.append(node) return isl isl_count = len(bridges) + 1 for i in reversed(sorted_bridges_ends): dfs(i, ag, isl_count) isl_count -= 1 dfs(start, ag, isl_count) return isl def bypasses(edges, bridges, islands, ds, dt): result = {(u, v): math.inf for u, v in bridges.keys()} island_to_bridge = {min(islands[u], islands[v]): (u, v) for u, v in bridges} edges_to_iterate = {(u, v): dist for u, v, dist in edges if (u, v) not in bridges.keys() and (v, u) not in bridges.keys()} for (u, v) in edges_to_iterate.keys(): if islands[u] < islands[v]: for i in range(islands[u], islands[v]): result[island_to_bridge[i]] = min(result[island_to_bridge[i]], ds[u] + edges_to_iterate[(u, v)] + dt[v]) if islands[v] < islands[u]: for i in range(islands[v], islands[u]): result[island_to_bridge[i]] = min(result[island_to_bridge[i]], ds[v] + edges_to_iterate[(u, v)] + dt[u]) return result ds = min_path_length(graph, start, finish) dt = min_path_length(graph, finish, start) opt = ds[finish] opt_edges = optimal_edges(edges, ds, dt, opt) br = bridges(opt_edges, ds, opt) ag = arrowed_graph(edges, ds) isl = islands(ag, br) bp = bypasses(edges, br, isl, ds, dt) for u, v in queries: if (u, v) in br: print(bp[(u, v)] if bp[(u, v)] < math.inf else 'Infinity') elif (v, u) in br: print(bp[(v, u)] if bp[(v, u)] < math.inf else 'Infinity') else: print(opt) c C# C++ HackerRank Solutions java javascript python CcppCSharpHackerrank Solutionsjavapython