Given an unweighted directed graph with N vertices and M edges and array A[] of size N. Given Q queries of the form (U, V), the task for this problem is for every query to print the shortest path from U to V and print the maximum coins collected for that shortest path. For visiting, Node ‘i’ collects A[i] coins. If traveling from U to V is not possible print -1.
Examples:
Input: N = 5, Edg[] = {{1, 2}, {1, 3}, {2, 3}, {3, 4}, {3, 5}, {4, 1}, {5, 1}}, A[] = {30, 50, 70, 20, 60}, Q[] = {{1, 3}, {3, 1}, {4, 5}};
Output: 1 100
2 160
3 180
Explanation:
- Length of Shortest path from 1 to 3 is 1 (1 -> 3) and coins collected = coins at node1 + coins at node3 = 30 + 70 = 100
- Length of Shortest path from 3 to 1 is 2 (3 -> 5 -> 1) and coins collected = coins at node3 + coins at node5 + coins at node1 = 70 + 60 + 30 = 160
- Length of Shortest path from 4 to 5 is 3 (4 -> 1 -> 3 -> 5) and coins collected = coins at node4 + coins at node1 + coins at node3 + coins at node5 = 20 + 30 + 70 + 60 = 180
Input: N2 = 2, Edg[] = {}, A[] = {100, 100}, Q[] = {{1, 2}}
Output: -1
Naive approach: The basic way to solve the problem is as follows:
The basic way to solve this problem is to generate all possible combinations by using a recursive approach.
Time Complexity: O(N!)
Auxiliary Space: O(1)
Efficient Approach: The above approach can be optimized based on the following idea:
Dynamic programming can be used to solve this problem
dp[i][j] represents shortest path from i to j.
Follow the steps below to solve the problem:
- Create dp[N][N] and ANS[N][N] tables with all values set to INT_MAX and INT_MIN.
- Iterate over all M edges and for each edge U and V set dp[U][V] to 1 and ANS[U][V] to A[U] + A[V].
- Fill the dp[N][N] table by iterating on all states.
- Iterate each query and print the answer
Below is the implementation of the above approach:
C++
// C++ code for the above approach:#include <bits/stdc++.h>using namespace std;// To avoid overflow#define int long long// Function for finding shortest paths// with maximized coinsvoid shortPath(int N, vector<vector<int> >& edg, vector<int>& A, vector<vector<int> >& Q){ // Initializing dp table for // finding shortest path vector<vector<int> > dp(N + 1, vector<int>(N + 1, INT_MAX)); // Initializing another table // to store max coins vector<vector<int> > ans(N + 1, vector<int>(N + 1, INT_MIN)); // Iterating over all M edges for (int i = 0; i < edg.size(); i++) { // There is edge exists from // edg[i][0] to edg[i][1] dp[edg[i][0]][edg[i][1]] = 1; // Answer variable stores ans[edg[i][0]][edg[i][1]] = A[edg[i][0] - 1] + A[edg[i][1] - 1]; } // Inserting from 1 to N for (int k = 1; k <= N; k++) { // Iterating on all 1 to N for (int i = 1; i <= N; i++) { // Iterating on all 1 to N for (int j = 1; j <= N; j++) { // If path through k is // shortest then relax // the weight if (dp[i][j] > dp[i][k] + dp[k][j]) { dp[i][j] = dp[i][k] + dp[k][j]; ans[i][j] = ans[i][k] + ans[k][j] - A[k - 1]; } // Maximise coins else if (dp[i][j] == dp[i][k] + dp[k][j] and ans[i][j] < ans[i][k] + ans[k][j] - A[k - 1]) { ans[i][j] = ans[i][k] + ans[k][j] - A[k - 1]; } } } } // Iterating for all queries for (int i = 0; i < Q.size(); i++) { // Query int U = Q[i][0], V = Q[i][1]; // Printing answer for query // if it exists if (dp[U][V] <= N * N) cout << dp[U][V] << " " << ans[U][V] << endl; // If no path exists else cout << "-1" << endl; }}// Driver programint32_t main(){ // Test case 1 int N1 = 5; vector<vector<int> > edg1 = { { 1, 2 }, { 1, 3 }, { 2, 3 }, { 3, 4 }, { 3, 5 }, { 4, 1 }, { 5, 1 } }; vector<int> A1 = { 30, 50, 70, 20, 60 }; vector<vector<int> > Q1 = { { 1, 3 }, { 3, 1 }, { 4, 5 } }; // Call for test case 1 shortPath(N1, edg1, A1, Q1); cout << endl; // Test case 2 int N2 = 2; vector<vector<int> > edg2 = {}; vector<int> A2 = { 100, 100 }; vector<vector<int> > Q2 = { { 1, 2 } }; // Call for test case 2 shortPath(N2, edg2, A2, Q2); return 0;} |
Java
//Java code for the above approachimport java.util.Arrays;class GFG { static void shortPath(int N, int[][] edg, int[] A, int[][] Q) { // Initializing dp table for finding shortest path int[][] dp = new int[N + 1][N + 1]; int[][] ans = new int[N + 1][N + 1]; for (int i = 0; i < edg.length; i++) { dp[edg[i][0]][edg[i][1]] = 1; ans[edg[i][0]][edg[i][1]] = A[edg[i][0] - 1] + A[edg[i][1] - 1]; } // Initializing another table to store max coins for (int k = 1; k <= N; k++) { for (int i = 1; i <= N; i++) { for (int j = 1; j <= N; j++) { if (dp[i][k] > 0 && dp[k][j] > 0) { // check if i and k, and k and j are // connected if (dp[i][j] == 0 || dp[i][j] > dp[i][k] + dp[k][j]) { dp[i][j] = dp[i][k] + dp[k][j]; ans[i][j] = ans[i][k] + ans[k][j] - A[k - 1]; } else if (dp[i][j] == dp[i][k] + dp[k][j] && ans[i][j] < ans[i][k] + ans[k][j] - A[k - 1]) { ans[i][j] = ans[i][k] + ans[k][j] - A[k - 1]; } } } } } for (int i = 0; i < Q.length; i++) { // Printing answer for query // if it exists int U = Q[i][0]; int V = Q[i][1]; if (dp[U][V] > 0 && dp[U][V] <= N * N) { System.out.println(dp[U][V] + " " + ans[U][V]); } else { // If no path exists System.out.println("-1"); } } } // Driver program public static void main(String[] args) { // Test case 1 int N1 = 5; int[][] edg1 = { {1, 2}, {1, 3}, {2, 3}, {3, 4}, {3, 5}, {4, 1}, {5, 1} }; int[] A1 = {30, 50, 70, 20, 60}; int[][] Q1 = { {1, 3}, {3, 1}, {4, 5} }; // Call for test case 1 shortPath(N1, edg1, A1, Q1); System.out.println(); // Test case 2 int N2 = 2; int[][] edg2 = {}; int[] A2 = {100, 100}; int[][] Q2 = {{1, 2}}; // Call for test case 2 shortPath(N2, edg2, A2, Q2); System.out.println(); }}// This code is contributed by Pushpesh Raj. |
Python3
#Python code for the above approach:import sys# To avoid overflowsys.setrecursionlimit(10**7)def shortPath(N, edg, A, Q): # Initializing dp table for # finding shortest path dp = [[float("inf") for j in range(N + 1)] for i in range(N + 1)] # Initializing another table # to store max coins ans = [[-sys.maxsize for j in range(N + 1)] for i in range(N + 1)] # Iterating over all M edges for i in range(len(edg)): # There is edge exists from # edg[i][0] to edg[i][1] dp[edg[i][0]][edg[i][1]] = 1 # Answer variable stores ans[edg[i][0]][edg[i][1]] = A[edg[i][0] - 1] + A[edg[i][1] - 1] # Inserting from 1 to N for k in range(1, N+1): # Iterating on all 1 to N for i in range(1, N+1): # Iterating on all 1 to N for j in range(1, N+1): # If path through k is # shortest then relax # the weight if dp[i][j] > dp[i][k] + dp[k][j]: dp[i][j] = dp[i][k] + dp[k][j] ans[i][j] = ans[i][k] + ans[k][j] - A[k - 1] # Maximise coins elif (dp[i][j] == dp[i][k] + dp[k][j] and ans[i][j] < ans[i][k] + ans[k][j] - A[k - 1]): ans[i][j] = ans[i][k] + ans[k][j] - A[k - 1] # Iterating for all queries for i in range(len(Q)): # Query U = Q[i][0] V = Q[i][1] # Printing answer for query # if it exists if dp[U][V] <= N * N: print(dp[U][V], ans[U][V]) # If no path exists else: print("-1")# Test case 1N1 = 5edg1 = [[1, 2], [1, 3], [2, 3], [3, 4], [3, 5], [4, 1], [5, 1]]A1 = [30, 50, 70, 20, 60]Q1 = [[1, 3], [3, 1], [4, 5]]# Call for test case 1shortPath(N1, edg1, A1, Q1)print()# Test case 2N2 = 2edg2 = []A2 = [100, 100]Q2 = [[1, 2]]#Call for test case 2shortPath(N2, edg2, A2, Q2)print()#This code is contributed by shivamsharma215 |
C#
// C# code for the above approach:using System;class Program { static void shortPath(int N, int[][] edg, int[] A, int[][] Q) { // Initializing dp table for finding shortest path var dp = new int[N + 1, N + 1]; var ans = new int[N + 1, N + 1]; for (var i = 0; i < edg.Length; i++) { dp[edg[i][0], edg[i][1]] = 1; ans[edg[i][0], edg[i][1]] = A[edg[i][0] - 1] + A[edg[i][1] - 1]; } // Initializing another table to store max coins for (var k = 1; k <= N; k++) { for (var i = 1; i <= N; i++) { for (var j = 1; j <= N; j++) { if (dp[i, k] > 0 && dp[k, j] > 0) { // check if i and k, and k and j are // connected if (dp[i, j] == 0 || dp[i, j] > dp[i, k] + dp[k, j]) { dp[i, j] = dp[i, k] + dp[k, j]; ans[i, j] = ans[i, k] + ans[k, j] - A[k - 1]; } else if (dp[i, j] == dp[i, k] + dp[k, j] && ans[i, j] < ans[i, k] + ans[k, j] - A[k - 1]) { ans[i, j] = ans[i, k] + ans[k, j] - A[k - 1]; } } } } } for (var i = 0; i < Q.Length; i++) { // Printing answer for query // if it exists var U = Q[i][0]; var V = Q[i][1]; if (dp[U, V] > 0 && dp[U, V] <= N * N) { Console.WriteLine(dp[U, V] + " " + ans[U, V]); } else { // If no path exists Console.WriteLine("-1"); } } } // Driver program static void Main() { // Test case 1 var N1 = 5; var edg1 = new int[][] { new int[] { 1, 2 }, new int[] { 1, 3 }, new int[] { 2, 3 }, new int[] { 3, 4 }, new int[] { 3, 5 }, new int[] { 4, 1 }, new int[] { 5, 1 } }; var A1 = new int[] { 30, 50, 70, 20, 60 }; var Q1 = new int[][] { new int[] { 1, 3 }, new int[] { 3, 1 }, new int[] { 4, 5 } }; shortPath(N1, edg1, A1, Q1); // Call for test case 1 Console.WriteLine(); // Test case 2 var N2 = 2; var edg2 = new int[0][]; var A2 = new int[] { 100, 100 }; var Q2 = new int[][] { new int[] { 1, 2 } }; // Call for test case 2 shortPath(N2, edg2, A2, Q2); Console.WriteLine(); }} |
Javascript
// JavaScript code for the above approach:// Function for finding shortest paths// with maximized coinsfunction shortPath(N, edg, A, Q) { // Initializing dp table for // finding shortest path var dp = Array.from({length: N+1}, () => Array(N+1).fill(Number.POSITIVE_INFINITY)); // Initializing another table // to store max coins var ans = Array.from({length: N+1}, () => Array(N+1).fill(-Infinity)); // Iterating over all M edges for (var i = 0; i < edg.length; i++) { // There is edge exists from // edg[i][0] to edg[i][1] dp[edg[i][0]][edg[i][1]] = 1; // Answer variable stores ans[edg[i][0]][edg[i][1]] = A[edg[i][0] - 1] + A[edg[i][1] - 1]; } // Inserting from 1 to N for (var k = 1; k <= N; k++) { // Iterating on all 1 to N for (var i = 1; i <= N; i++) { // Iterating on all 1 to N for (var j = 1; j <= N; j++) { // If path through k is // shortest then relax // the weight if (dp[i][j] > dp[i][k] + dp[k][j]) { dp[i][j] = dp[i][k] + dp[k][j]; ans[i][j] = ans[i][k] + ans[k][j] - A[k - 1]; } // Maximise coins else if (dp[i][j] == dp[i][k] + dp[k][j] && ans[i][j] < ans[i][k] + ans[k][j] - A[k - 1]) { ans[i][j] = ans[i][k] + ans[k][j] - A[k - 1]; } } } } // Iterating for all queries for (var i = 0; i < Q.length; i++) { // Query var U = Q[i][0]; var V = Q[i][1]; // Printing answer for query // if it exists if (dp[U][V] <= N * N) { console.log(dp[U][V], ans[U][V]); } // If no path exists else { console.log("-1"); } }}// Driver program// Test case 1var N1 = 5;var edg1 = [[1, 2], [1, 3], [2, 3], [3, 4], [3, 5], [4, 1], [5, 1]];var A1 = [30, 50, 70, 20, 60];var Q1 = [[1, 3], [3, 1], [4, 5]];// Call for test case 1shortPath(N1, edg1, A1, Q1);console.log();// Test case 2var N2 = 2;var edg2 = [];var A2 = [100, 100];var Q2 = [[1, 2]];// Call for test case 2shortPath(N2, edg2, A2, Q2);console.log();// This code is contributed by Prasad Kandekar(prasad264) |
Output
1 100 2 160 3 180 -1
Time Complexity: O(N3)
Auxiliary Space: O(N2)
Related Articles:
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!