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

Intelligent Robber

PKJ
 Coding  Problem  Keys   Intelligent Robber    Problem Statement  There are N streets in a town and in each street there is one treasure house with certain number of gold coins - C(1) ... C(N) in it. As the robber is intelligent, in order not to get caught, if he robs in a house in a given street he does not rob in the houses in the two streets which are adjacent to the house robbed (either to it's left or right). Thus he avoid awareness among the people and his risk is reduced. Given N and the coins C(i) (where i=1 to N) in each of the treasure house, find the maximum gold coins M, that the robber can acquire.  Input Format  The first line contains N. The second line contains N positive integers representing the gold coins in each of the N treasure houses.  Output Format  The first line contains M which represents the maximum number of gold coins the robber can acquire.  Boundary Conditions  3 <= N <= 999999. 1...
Click to Continue...

String Rotation Odd and Even Positions

PKJ
 Coding Problem Keys   String Rotation Odd and Even Positions   Problem Statement  A string S and two integers M and N are passed as input. The program must rotate the characters present in the odd positions of the string M times and rotate characters present in the even positions of the string N times.  Boundary Condition(s)  2 <= Length of the string <= 1000. 1 <= M, N <= 1000.  Input Format  The first line contains the values of S, M and N separated by space(s).  Output Format  The first line contains the rotated string.  Example Input/Output 1   Input  technology 2 3  Output  logotycenh  Explanation  The characters present in the odd positions are 'tcnlg'. When rotated 2 positions, the value is 'lgtcn'. The characters present in the even position are 'ehooy', When rotated 3 positions, the value is 'ooyeh'. Hence the rotated string value is 'logotycenh'.  Example Input...
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...

Octal Equivalent of N

PKJ
 Coding Problem Keys   Octal Equivalent of N   Problem Statement  Given an integer N as input, the program must print the octal equivalent of N.  Boundary Condition(s)  1 <= N <= 10000000  Input Format  The first line contains the value of N.  Output Format  The first line contains the octal equivalent of N.  Example Input/Output 1   Input  4756  Output  11224  Explanation  The octal equivalent of 4756 is 11224.  Example Input/Output 2   Input  49467  Output  140473  Explanation  The octal equivalent of 49467 is 140473.  Note:  Max Execution Time Limit: 5000 millisecs   Solution   Programming Language: Python 3 Language  print ( oct ( int ( input ()))[ 2 :]) # Published By PKJCODERS  Alter  def decimal_to_octal (decimal): octal = 0 i = 1 while (decimal != 0 ): octal =...
Click to Continue...

Multiply By 2

PKJ
 Coding  Problem  Keys   Kick Start   Multiply By 2    Problem Statement  The program must accept a number and multiply it by 2.  Example Input/Output 1   Input  10  Output  20  Example Input/Output 2   Input  50  Output  100  Note:  Max Execution Time Limit: 4000 millisecs   Solution   Programming Language: C Language  #include <stdio.h> #include <stdlib.h> int main (){ int n; scanf( "%d" ,&n); printf( "%d" ,n* 2 ); } //Published By PKJCODERS  Programming Language: C++ Language  #include <iostream> using namespace std; int main (){ int n; cin>>n; cout<<n* 2 ; } //Published By PKJCODERS  Programming Language: Java Language  import java.util.* ; public class Hello { public static void main (String[] args) { Scanner sc = new Sc...
Click to Continue...

Even Integers - Even Positions

PKJ
 Coding Problem Keys   Even Integers - Even Positions   Problem Statement  The program must accept N integers as the input. The program must print all the even integers which are at the even positions as the output. If there is no even integer are even positions then the program must print -1 as the output.  Input Format  The first line contains the value N. The second line contains N integers separated by space(s).  Output Format  The first line contains the even integers which have occurred at the even positions each separated by space(s).  Boundary Condition(s)  1 <= N <= 10 ⁵ -99999 <= Each Integer Value <= 99999  Example Input/Output 1   Input  7 43 -49 -22 16 -86 78 77   Output  16 78   Explanation  The integers present at even positions are -49, 16 and 78. So the even integers are 16 and 78. Hence the output is 16 and 78.  Example Input/Output 2   Input...
Click to Continue...