![](https://csdnimg.cn/release/download_crawler_static/10591831/bg6.jpg)
* Input: From a user-specified file, the number of cities
* followed by the costs of travelling between the
* cities organized as a matrix: the cost of
* travelling from city i to city j is the ij entry.
* Costs are nonnegative ints. Diagonal entries are 0.
* Output: The best tour found by the program and the cost
* of the tour.
* Notes:
* 1. Costs and cities are non-negative ints.
* 2. Program assumes the cost of travelling from a city to
* itself is zero, and the cost of travelling from one
* city to another city is positive.
* 3. Note that costs may not be symmetric: the cost of travelling
* from A to B, may, in general, be different from the cost
* of travelling from B to A.
* 4. Salesperson's home town is 0.
* 5. The digraph is stored as an adjacency matrix, which is
* a one-dimensional array: digraph[i][j] is computed as
* digraph[i*n + j]
* 6. Define STATS at compile time to get some info on broadcasts
* of best tour costs.
* IPP: Exercise 6.21
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <mpi.h>
const int INFINITY = 1000000;
const int NO_CITY = -1;
const int FALSE = 0;
const int TRUE = 1;
const int MAX_STRING = 1000;
const int TOUR_TAG = 1;
const int INIT_COST_MSGS = 100;
typedef int city_t;
typedef int cost_t;
typedef struct {
city_t* cities; /* Cities in partial tour */
int count; /* Number of cities in partial tour */
cost_t cost; /* Cost of partial tour */
} tour_struct;
typedef tour_struct* tour_t;
#define City_count(tour) (tour->count)
#define Tour_cost(tour) (tour->cost)