travel_planning_problem.cpp

使用Floyd-Warshall最短路径及TSP的DP法解旅游规划问题

#include<iostream>
using namespace std;

typedef struct Min_Route{
  short r[13], len;
};

typedef struct Output_Route{
  short r[13*13+1], len;
};

//Varibles For Input
int N, M, K, DEFAULT_ROUTE[13], DIS_MATRIX[13][13];

inline void Initialize(){
  for(int i = 0;i < 13;i++)
		for(int j = 0;j < 13;j++)
    	DIS_MATRIX[i][j] = INT_MAX;
  for(int i = 0;i < 13;i++)
  	DIS_MATRIX[i][i] = 0;				
}

inline void ReadIn(){
	scanf("%d%d", &N, &M);
	for(int i = 0, a, b, d;i < M;i++){
	  scanf("%d%d%d", &a, &b, &d);
	  DIS_MATRIX[a][b] = DIS_MATRIX[b][a] = d;
	}
	scanf("%d", &K);
	for(int i = 0;i < K;i++)
	  scanf("%d", &DEFAULT_ROUTE[i]);	 
}

long long dis[13][13] = {};
int path[13][13];
	
inline void Floyd_Warshall(){	
  for(int i = 0;i < N;i++)
		for(int j = 0;j < N;j++){
      dis[i][j] = DIS_MATRIX[i][j];
      if(dis[i][j] == INT_MAX || i == j)
        path[i][j] = -1;
      else
        path[i][j] = i;
		}
  for(int k = 0;k < N;k++){ 
for(int i = 0;i < N;i++) 
      for(int j = 0;j < N;j++)
        if(dis[i][k] + dis[k][j] < dis[i][j])
          dis[i][j] = dis[i][k] + dis[k][j], path[i][j] = path[k][j];
  }
}

int min_dis = INT_MAX, route_stack[13] = {}, min_routes_top = 0;
Min_Route min_routes[1000000];
bool visited[13] = {};
int tsp[13+1][9000] = {}; //[np][visited_mask]

inline void DFS(int n, int p, int visited){
  if(tsp[p][visited] >= min_dis)
    return;
  if(n == K-1){
    if(tsp[p][visited] < min_dis){
      Min_Route t_mr;
      min_dis = tsp[p][visited];
      for(int i = 0;i < K;i++)
        t_mr.r[i] = route_stack[i];
      t_mr.len = min_dis;
      min_routes[min_routes_top++] = t_mr;
    }
	return;
  }
    
  for(int i = 1, k = 2, np;i < K;k <<= 1, i++){
	np = DEFAULT_ROUTE[i];
	if(!(visited&k) && (!tsp[i][visited|k] || dis[p][np]+tsp[p][visited] < tsp[i][visited|k]) ){
	  route_stack[n+1] = np;
	  tsp[i][visited|k] = dis[DEFAULT_ROUTE[p]][np]+tsp[p][visited];
	  DFS(n+1, i, visited|k);
    }
  }
}

inline void TSP(){
  route_stack[0] = DEFAULT_ROUTE[0];
  DFS(0, 0, 1);       
}

Output_Route out_route;

void Create_Complete_Route(){
  int p, stack[13], top, LEN = 0, S, T;
	for(int i = 0;i < min_routes_top;i++){
    if(min_routes[i].len == min_dis){
  		for(int j = 0;j < K-1;j++){
  			S = min_routes[i].r[j], T = min_routes[i].r[j+1];
        top = 0;
        p = path[S][T];
        do{
	        stack[top++] = p;
  	   	  p = path[S][p];	 
        }while(p != -1);
        for(int k = 0;k < top;k++){
  	 	    out_route.r[k+LEN] = stack[top-k-1];
				}
	      LEN += top;
	    }
	    out_route.r[LEN] = min_routes[i].r[K-1];
			out_route.len = LEN+1;
			return;
	  }  
  }
} 

inline void Output(){
  printf("Minimum travel distance: %d\n", min_dis);
  printf("Travel route:");
  for(int i = 0;i < out_route.len;i++)
    printf(" %d", out_route.r[i]);
}

int main(){
  Initialize();
  ReadIn();
  Floyd_Warshall();
  TSP();
  Create_Complete_Route();
  Output();
  system("pause");
}