1150. Travelling Salesman Problem.md

【PAT A-1150】Travelling Salesman Problem

题意概述

本题描述的是巡回收货商问题：给出一个城市列表以及每对城市之间的距离，求每个城市均被访问之后再返回原城市的最短路径。显然，整个路径会构成一个环。本题中，你需要从给定的环中找到最接近旅行商问题的解的环。

输入输出格式

输入第一行包含 2 个正整数 N 和 M，分别表示无向图的顶点个数和边的个数。接下来 M 行，每行通过给出两个结点的编号以及这两个结点之间的距离，表示这两个结点之间存在一条边。其中顶点从 1 到 N 编号。接下来一行给出一个正整数 K，表示查询的数量。然后是 K 行查询，每行以$n\ V_1\ V_2\cdots V_n$的格式给出一个路径的顶点序列。

对于每个路径，首先以Path X: TotalDist (Description)的格式打印一行，其中 X 是该路径的编号（从 1 开始），TotalDist 是路径的总长度（如果不存在此距离，则输出 NA），并且 Description 为以下文字描述之一：

1. 如果给定的路径是包含所有顶点的简单环，则为TS simple cycle；
2. 如果给定的路径是包含所有顶点的环，但不是简单环，则为TS cycle；
3. 如果给定的路径不是包含所有顶点的环，则为Not a TS cycle；

最后一行以Shortest Dist(X) = TotalDist格式打印，其中 X 是最接近旅行商问题解决方案的路径编号，TotalDist 是其总长度。题目保证这个解是唯一的。

数据规模

$$2<N \le 200$$

算法设计

针对一个路径，判断的过程可以是这样的：

1. 如果路径中某两个相邻结点之间没有边，或首尾结点不相同（即不能构成一个环），或没有包含图中所有顶点，输出Not a TS cycle；
2. 否则，如果路径中，首尾结点出现出现两次，其它结点出现 1 次，则为TS simple cycle；
3. 否则为TS cycle。

还要注意，在统计最短距离时，属于Not a TS cycle的路径不要统计在内。

C++代码

#include <bits/stdc++.h>
using namespace std;
using gg = long long;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    gg ni, mi, ki;
    cin >> ni >> mi;
    vector<vector<gg>> graph(ni + 1, vector<gg>(ni + 1));
    while (mi--) {
        gg ai, bi, ci;
        cin >> ai >> bi >> ci;
        graph[ai][bi] = graph[bi][ai] = ci;
    }
    cin >> mi;
    gg num = -1, dis = INT_MAX;
    for (gg ii = 1; ii <= mi; ++ii) {
        cout << "Path " << ii << ": ";
        cin >> ki;
        vector<gg> v(ki);
        for (gg& i : v) {
            cin >> i;
        }
        gg curdis = 0;
        unordered_set<gg> us{v[0]};
        for (gg i = 1; i < v.size(); ++i) {  //判断每两个顶点之间是否有边
            if (graph[v[i]][v[i - 1]] == 0) {  //两个顶点之间没有边
                cout << "NA (Not a TS cycle)\n";
                goto loop;
            }
            us.insert(v[i]);
            curdis += graph[v[i - 1]][v[i]];
        }
        if (v.front() != v.back() or us.size() != ni) {  //不是TS环
            cout << curdis << " (Not a TS cycle)\n";
        } else {
            if (us.size() != v.size() - 1) {  //不是TS简单环
                cout << curdis << " (TS cycle)\n";
            } else {
                cout << curdis << " (TS simple cycle)\n";
            }
            if (curdis < dis) {
                dis = curdis;
                num = ii;
            }
        }
    loop:;
    }
    cout << "Shortest Dist(" << num << ") = " << dis;
    return 0;
}