c++ programing question25: Shortest Path Tree Time Limit: 1 seconds Problem Desc

Question

c++ programing question25:

Shortest Path Tree

Time Limit: 1 seconds

Problem Description
Given a graph with positive edge weight and a source s, find a spanning tree such that the the
d_T(s,v)=d(s,v) for each vertex v and the total tree edge weight is minimized.
Total weight of the tree.
d_T(s,v) is the distance from s to v on T, and d(s,v) is the distance on the original graph
Input File Format
There will be a positive integer T at the beginning, which means that there will be T input data.
The first line of input data has three positive integers n, m, and q, representing n points and m edges on the graph, 2 ? n ? 10000, 1 ? m
? 500000, each point is numbered 0 ~ n-1, q is the number of queries.
The next m rows each have three positive integers u, v, and w, which represent an edge from u to v with a weight w, 0 < w <1000.
Then there will be q rows, each with an integer r, representing that a shortest path tree is generated at point r and the weights of all the edges of the tree are summed.
The shortest path tree may not be unique, so must select the one that has the smallest sum of edges' weight.
Output Format

for each input data output q answers, each answer in independent line.

Explanation / Answer

#include<iostream>
#include<conio.h>
#include<stdlib.h>

main()
{
  
   int m,c,x,y,input,st,q,t,cost[10][10],i,j,k,n,stk[10],top,v,predecessor[10],reached[10],totalcost=0;;
   cout<<"Enter total number of input";
   cin>>input;                                                // Number of Inputs
   for(t=1;t<=input;t++)
   {
   cout <<"enterno of vertices";
   cin >> n;                                                   //Number of vertices
   cout <<"enter no of edges";
   cin >> m;                                                  //Number of edges
   cout<<"enter number of queries";
   cin>>q;                                                   //Number of queries
   for(i=1;i<=n;i++)
   {
       for(j=1;j<=n;j++)
       cost[i][j]=0;
   }
   cout <<" EDGES Cost ";
   for(k=1;k<=m;k++)                                           //Edges cost
   {
       cin >>i>>j>>c;
       cost[i][j]=c;
       cost[j][i]=c;
   }
       for(i=1;i<=n;i++)
   {
       for(j=1;j<=n;j++)
       if(cost[i][j]==0)
       cost[i][j]=555;
   }
  
   for(t=1;t<=q;t++)
   {
      cout<<"enter starting vertex";                                        // Starting vertex for each query
      cin>>st;
   for(i=1;i<=n;i++)
   predecessor[i]=0;
       for(i=1;i<=n;i++)
   reached[i]=0;

   reached[st]=1;                                                             //initial reachable node
  
   predecessor[st]=0;                                                         //initial spanning tree is null

   for ( k = 1; k < n; k++)                                                    //loop n-1 times
     {
  
   x = st;
   y = 1;

   for ( i = 1; i <= n; i++ )
  
{
            for ( j = 1; j <= n; j++ )
            {
                  if (( reached[i]==1) && (reached[j]==0))
               {
                  
               if(cost[i][j] < cost[x][y] )
       {
      
                   x = i;                                                // (i,j) has lower cost
                   y = j;
                
                   cout<<"x="<<x;
                   cout<<"y="<<y;
               }
       }
            }
    }
      
        totalcost+=cost[x][y];
       predecessor[y] = x;                                              // link with minimum cost
   reached[y] = true;                                                  

    }
    
cout<<"total cost="<<totalcost;                                             //print total cost
}
}
}
   

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.