Relay Race is a great team game that has attracted generations of Bytelandian children.
Team members are numbered from 0 upto N-1 for a team of N persons. In the game there is a baton(a short stick) which is initially in the hands of the captain (0 numbered person) and the baton needs to be transferred to the K numbered person by passing through all the team members. The game will end when the baton will be in the hands of the K numbered person.
-> Each of the team member can run and pass the baton to every other team member and all the team members are initially standing at a given fixed distance from the other members.
->Every team wants to minimize the total distance traversed by its members by the end of game.
-> The baton must pass through each team member exactly once.
Find the minimum distance required for transferring the baton from the captain to the K numbered person by passing through each team member exactly once.
Input
First line contains two space separated integers N and K denoting the number of team members and the number of the person which will end the game. The next (N*(N-1))/2 lines contain 3 space separated integers A B D denoting that the distance between the members numbered A and B is D units.
Output
Output an integer denoting the least distance required to complete the race.
Constraints
2 <= N <= 20
0 <= A,B <= 19
1 <= D <= 10^6.
program
Sample Input (Plaintext Link)
5 4
0 1 4
0 2 3
0 3 6
0 4 10
1 2 4
1 3 5
1 4 5
2 3 3
2 4 7
3 4 8
expected output:
16
Path giving the minimum distance is 0 -> 2 -> 3 -> 1 -> 4
And minimum distance is given by dist(0,2) + dist(2,3) + dist(3,1) + dist(1,4) i.e. 3 + 3 + 5 + 5 = 16
#include<iostream>
using namespace std;
int d[20];
int counts=0;
long int ans[20];
long int findd(long int a[][20],int r,int nc) //function to find the min element in r row
{ int check(int); //function to check if the given index is already visited
int k;
long int mind=0; //to store the min no.
for(k=0;k<nc;++k)
{ if(mind>a[r][k]&&check(k))
mind=a[r][k];
}
return mind;
++counts;
d[counts]=k;
}
int check(int j) // to check if index j is already visited
{ int i;
if(counts==0)
{d[0]=0;
return 1;}
else
for(i=0;i<counts;++i)
{
if(d[i]==j)
return 0;
}
}
int main()
{ void cal(int f,int n,long int dist[][20]);
int fcount=counts;
int n,f;
cin>>n>>f;
long int findd(long int a[][20],int r,int nc);
long int dist[n][n];
int t=(n*(n-1))/2;
while(t)
{
int i,j;
cin>>i;
cin>>j;
cin>>dist[i][j];
dist[i][j]=dist[j][i];
–t;
}
cal(f,n,dist);
long int sum=0;
for(int g=0;g<counts;++g)
{
sum=sum+ans[g];
}
cout<<sum;
}
void cal(int f,int n,long int dist[][20])
{ int fcount=0;
int p=0;
while(p!=f)
{
ans[fcount]=findd(dist,p,n);
++fcount;
}
ans[fcount]=findd(dist,f,n);
}