Write a program in C or C++ for computing min cost arborescence.
INPUT:
First line: Number of Test Cases T and then follows their description
For each test case, first row indicate N s (single space separated) where N is number of vertices in directed graph where vertices are labelled 1 to N and s is the index of source vertex
Second row mentions the number of edges M
And then M rows mentioning u , v , w(u,v)
Output Format
T rows corresponding to T test cases
Output row for each test case has N+1 entries
where first entry is the total sum of min cost arborescence and then N entries corresponding to vertices V1, V2, V3…, VN providing the distance of ith vertex from the source vertex s.
============INPUT ===========
2
6 1
9
1 2 10
1 3 2
1 4 10
2 3 1
3 4 4
4 5 2
2 6 8
5 2 2
4 6 4
8 1
13
1 2 5
1 5 11
5 2 6
6 5 10
6 2 2
2 3 3
2 7 13
7 6 7
3 7 9
3 4 12
4 8 1
8 3 4
7 8 8
============OUTPUT ===========
14 0 10 2 6 8 10
47 0 5 8 20 34 24 17 21
I am not able to solve this question.
I am stuck with the loop in which all relative costs will be zero.
How to solve this question?