Shortest Path in Tree

PKJ

 Coding Problem Keys 

 Shortest Path in Tree 

 Problem Statement 

Given a weighted undirected graph T consisting of nodes valued [0, N-1] and an array Edges[][3] of type {u, v, w} that denotes an edge between vertices u and v having weight w. The task is to find the sum of all pair shortest paths in the given tree.

 Input Format 

The first line consists of 2 integers denoting N (No. of Nodes) and E (No. of Edges).
Next, E lines consists of 3 integers denoting u, v, w.

 Output Format 

The first line contains the sum of all pair shortest paths in the given tree.

 Sample Input/Output 1 

 Input 

3 2
0 2 15
1 0 90

 Output 

210

 Explanation 

Sum of weight of the path between nodes 0 and 1 = 90
Sum of weight of the path between nodes 0 and 2 = 15
Sum of weight of the path between nodes 1 and 2 = 105
Hence, sum = 90 + 15 + 105

 Sample Input/Output 2 

 Input 

4 3
0 1 1
1 2 2
2 3 3

 Output 

20

 Explanation 

Sum of weight of the path between nodes 0 and 1 = 1
Sum of weight of the path between nodes 0 and 2 = 3
Sum of weight of the path between nodes 0 and 3 = 6
Sum of weight of the path between nodes 1 and 2 = 2
Sum of weight of the path between nodes 1 and 3 = 5
Sum of weight of the path between nodes 2 and 4 = 3
Hence, sum = 1 + 3 + 6 + 2 + 5 + 3 = 20

 Solution 

 Programming Language: C++ Language 

#include <iostream>
using namespace std;
#define INF 99999
int check(int* graph, int v){
    int arr[v][v],i,j,k;
    for(i=0;i<v;i++){
        for(j=0;j<v;j++){
            arr[i][j]=*((graph+i*v)+j);
        }
    }
    for(k=0;k<v;k++){
        for(i=0;i<v;i++){
            for(j=0;j<v;j++){
                if(arr[i][k]+arr[k][j]<arr[i][j]){
                    arr[i][j]=arr[i][k]+arr[k][j];
                }
            }
        }
    }
    int sum=0;
    for(i=0;i<v;i++){
        for(j=i+1;j<v;j++){
            sum+=arr[i][j];
        }
    }
    return sum;
}
int main(){
    int n,e;
    cin>>n>>e;
    int arr[e][3];
    for(int i=0;i<e;i++){
        for(int j=0;j<3;j++){
            cin>>arr[i][j];
        }
    }
    int g[n][n];
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            g[i][j]=INF;
        }
    }
    for(int i=0;i<e;i++){
        int u=arr[i][0];
        int v=arr[i][1];
        int w=arr[i][2];
        g[u][v]=w;
        g[v][u]=w;
    }
    cout<<check((int*)g,n);
    return 0;
}

// Published By PKJCODERS

 (Note: Incase If the code doesn't Pass the output kindly comment us with your feedback to help us improvise.) 

Comments

Post a Comment

Popular Posts

Cut Down & Plant - Trees

PKJ
 Coding Problem Keys   Cut Down & Plant - Trees   Problem Statement  In a garden, there are N trees from left to right. The height of each tree is passed as input to the program. The gardener wants to cut down T trees completely from left to right, but if he cuts a tree of height H, then he must plant certain number of trees based on the following conditions.     - If H is odd, then he must plant H trees of height ranging from 1 to H on the rightmost end.     - If H is even, then he must plant H/2 trees of height ranging from H/2 to 1 on the rightmost end. The value of T is also passed as the input to the program. The program must print the number of trees remaining in the garden after cutting down T trees as the output.  Boundary Condition(s)  1 <= N <= 100. 1 <= Height of each tree <= 50. 1 <= T <= 1000.  Input Format  The first line contains N. The second line contains N integer values se...
Click to Continue...

Both Adjacent Elements - Odd or Even

PKJ
 Coding Problem Keys   Both Adjacent Elements - Odd or Even   Problem Statement  The program must accept N integers as the input. The program must print the integers that have both the adjacent integer values as odd or even. At least one integer will have both the adjacent values as odd or even among the N integers. (The first and last integers have only one integer adjacent to them. So consider only the single adjacent integer for them).  Boundary Condition(S)  3 <= N <=100 -10 ⁷ <= Each integer value <= 10 ⁷  Input Format  The First line contains the value of N. The Second line contains the N integers separated by space(s).  Output Format  The First line contains the integers (which have both the adjacent element values as odd or even) separated by a space.  Example Input/Output 1   Input  7 10 21 20 33 98 66 29  Output  10 21 20 33 29  Example Input/Output 2   Input...
Click to Continue...

Sum of Digits - Largest Integer

PKJ
 Coding Problem Keys   Sum of Digits - Largest Integer   Problem Statement  The program must accept an integer  N  as the input. The program must print the sum of the digits of the largest integer among the N integers as the output.  Input Format  The first line contains the value of integer N. The second line contains N integers separated by space(s).  Output Format  The first line contains the sum of the digits of the largest integer among N integers.  Boundary Condition(s)  1 <= N <= 100 1 <= Each Integer Value <= 1000  Example Input/Output 1   Input  6 98 74 85 23 58 21   Output  17  Explanation  The largest integer is 98 . So the sum of the digits of 98 is 17 (9 + 8). Hence the output is 17.  Example Input/Output 2   Input  9 401 884 8 203 123 950 475 520 193   Output  14  Max Execution Time Limit: 4000 millisecs   S...
Click to Continue...

Unique Element

PKJ
 Coding Problem Keys   Unique Element   Problem Statement  You will be given N numbers, N > 0. All integer elements will be repeated one or more times except for one element which is unique. Identify the unique element and print it out.  Input  First line is an integer N, representing the total count. Second line, contains space separated integer array A.  Output Format  One integer, representing the unique element from the given set of elements.  Constraints  N <= 1000  Example Input/Output 1   Input  12 1 5 7 2 5 5 1 7 7 1 5 1  Output  2  Example Input/Output 2   Input  16 1 1 1 2 3 4 5 5 5 1 1 3 4 1 2 6  Output  6  Solution   Programming Language: Python 3 Language  n= int ( input ()) arr= list ( map ( int , input ().split())) d={} temp= list ( set (arr)) for i in temp: d[i]=arr.count(i) x= list (d.keys()) y= list (d.values())...
Click to Continue...

K'th Largest Number

PKJ
 Coding Problem Keys   K'th Largest Number   Problem Statement  Write a code to find the K'th largest number in a given array. For example, If k = 2, find the second largest number in the given array.  Input Format  The first line contains the value of N. The second line contains the N values of the given array. The third line contains the value of K.  Output Format  Prints the K'th largest number in the given array.  Sample Input  n = 6 arr[] = {5, 7, 12, 23, 48, 17} k = 4  Sample Output  12  Solution   Programming Language: Python 3 Language  n= int ( input ()) arr= list ( map ( int , input ().split())) arr.sort() arr=arr[::- 1 ] k= int ( input ()) print (arr[k- 1 ],end= " " ) # Published By PKJCODERS  Programming Language: C++ Language  #include<bits/stdc++.h> using namespace std; int main (){ int n; cin>>n; int arr[n]; for ( int i= 0 ;i<...
Click to Continue...

Number of Profitable Days

PKJ
 Coding Problem Keys   Number of Profitable Days   Problem Statement  The e-commerce company " TodaysApparel " has a list of sales values of N days. Some days the company made a profit, represented as a positive sales value. Other days the company incurred a loss, represented as a negative sales value. The company wishes to know the number of profitable days in the list. Write a algorithm to help the company know the number of profitable days in the list.  Input Format  The first line of input consists of an integer - numDays representing the number of days (N). The second line of input consists of N space-separated integers - sales[0], sales[1] .............. sales[N-1] representing the sales values of N days respectively.   Output Format  Print an integer representing the number of days the company made a profit.  Example Input/Output 1   Input  7 23 -7 13 -34 56 43 -12   Output  4   Explanation ...
Click to Continue...