PAT A1150 Travelling Salesman Problem

1150 Travelling Salesman Problem

分数 25

作者 CHEN, Yue

单位 浙江大学

The "travelling salesman problem" asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city and returns to the origin city?" It is an NP-hard problem in combinatorial optimization, important in operations research and theoretical computer science. (Quoted from "https://en.wikipedia.org/wiki/Travelling_salesman_problem".)

In this problem, you are supposed to find, from a given list of cycles, the one that is the closest to the solution of a travelling salesman problem.

Input Specification:

Each input file contains one test case. For each case, the first line contains 2 positive integers N (2City1 City2 Dist, where the cities are numbered from 1 to N and the distance Dist is positive and is no more than 100. The next line gives a positive integer K which is the number of paths, followed by K lines of paths, each in the format:

n C1​ C2​ ... Cn​

where n is the number of cities in the list, and Ci​'s are the cities on a path.

Output Specification:

For each path, print in a line Path X: TotalDist (Description) where X is the index (starting from 1) of that path, TotalDist its total distance (if this distance does not exist, output NA instead), and Description is one of the following:

• TS simple cycle if it is a simple cycle that visits every city;
• TS cycle if it is a cycle that visits every city, but not a simple cycle;
• Not a TS cycle if it is NOT a cycle that visits every city.

Finally print in a line Shortest Dist(X) = TotalDist where X is the index of the cycle that is the closest to the solution of a travelling salesman problem, and TotalDist is its total distance. It is guaranteed that such a solution is unique.

Sample Input:

6 10
6 2 1
3 4 1
1 5 1
2 5 1
3 1 8
4 1 6
1 6 1
6 3 1
1 2 1
4 5 1
7
7 5 1 4 3 6 2 5
7 6 1 3 4 5 2 6
6 5 1 4 3 6 2
9 6 2 1 6 3 4 5 2 6
4 1 2 5 1
7 6 1 2 5 4 3 1
7 6 3 2 5 4 1 6

Sample Output:

Path 1: 11 (TS simple cycle)
Path 2: 13 (TS simple cycle)
Path 3: 10 (Not a TS cycle)
Path 4: 8 (TS cycle)
Path 5: 3 (Not a TS cycle)
Path 6: 13 (Not a TS cycle)
Path 7: NA (Not a TS cycle)
Shortest Dist(4) = 8

 

* 是旅行商问题的必要条件是所有顶点都要被访问过至少一次，至于是简单回路
 * 还是复杂回路，就看路径回到起点的回路条数；
 * 如果路径不存在或者有顶点没有被访问到，那么就不是旅行商回路；

/**
 * 是旅行商问题的必要条件是所有顶点都要被访问过至少一次，至于是简单回路
 * 还是复杂回路，就看路径回到起点的回路条数；
 * 如果路径不存在或者有顶点没有被访问到，那么就不是旅行商回路；
*/
 
#include <iostream>
#include <algorithm>
 
using namespace std;
 
const int N = 210, INF = 1e9;
int g[N][N]; //存储图
bool hs[N];
int Nv, Ne; //顶点数，边数
 
void Read()
{
    fill(*g, *g + N * N, INF); //初始化
    cin >> Nv >> Ne;
    for(int i=0; i<Ne; ++i)
    {
        int u, v, w;
        cin >> u >> v >> w;
        g[u][v] = g[v][u] = min(g[u][v], w);
    }
 
    int k;
    cin >> k;
    
    int MIN = INF, idx = -1;
    
    for(int i=1; i<=k; ++i)
    {
        fill(hs, hs+N, 0); //初始化，统计已被访问过的顶点编号
        
        //pre记录上一次的顶点编号，ori记录起点，dis记录路径长度
        int pre, ori = -1, dis = 0;
        int cnt = 0; //cnt记录回路条数
        
        int m;
        cin >> m;
        
        for(int j=0; j<m; ++j)
        {
            int u;
            cin >> u;  
            if(j != 0)
            {
                if(g[pre][u] != INF)
                    dis += g[pre][u];
                else
                    dis = INF; //路径不存在
            }
            else
                ori = u;
            
            hs[u] = 1; //记录u点已被访问过
            
            //如果形成一条回路，cnt加一
            if(j != 0 && u == ori)    ++cnt; 
            pre = u;  
        }
        
        for(int j=1; j<=Nv; ++j)
            if(hs[j] == 0)
                cnt = 0; //如果有顶点没有被访问过
        
        printf("Path %d: ", i);
        if(dis >= INF)  
        {
            printf("NA ");
            cnt = 0; //如果dis >= INF, 那么一定是不存在路径的情况
        }
        else printf("%d ", dis);
        
        if(cnt == 0)    puts("(Not a TS cycle)");
        else if(cnt == 1)   puts("(TS simple cycle)");
        else puts("(TS cycle)");
        
        if(cnt && dis < MIN)   
        {
            MIN = dis;
            idx = i;
        }
    }
    
    printf("Shortest Dist(%d) = %d\n", idx, MIN);
}
 
int main()
{
    Read();
    
    return 0;
}