Travelling Salesman Problem $($TSP$)$: Given a set of cities and distance between every pair of cities, the problem is to find the shortest possible route that visits every city exactly once and returns to the starting point.

For example, consider the graph shown below. A TSP tour in the graph is $1-2-4-3-1.$ The cost of the tour is $10+25+30+15$ which is $80.$

The data is provided in file showing distance between all the nodes. The number of nodes can vary but make sure to attach the testFile while submitting your code.

testFile.txt

$4$

$1-210$

$1-315$

$1-420$

$2-335$

$2-425$

$3-430$

Take a number N from user and create N different threads. Each thread will find a solution of TSP by randomly generating numbers $($Make sure the sequence of random numbers generated by different thread is not the same$).$ Now each thread will save their output $($cost of the tour$)$ in a global array $($after displaying it on terminal along$-$with their thread id$).$ When all threads will be done computing the value, they will check whether their value was the minimum cost or not. The threads whose solution was not shortest will be stuck in an infinite loop. The one with shortest solution will output the thread id and cancel all the remaining threads.

If two threads have the same value, then define a mechanism as tiebreaker and explain it in comment on the top of your code file.

provide the code for above in c language