Pat class a 1150 traveling salesman problem

Original link

“ Travel agent problem ” It's such a question ：“ Give a list of cities and the distance between each pair of cities , What is the shortest way to visit each city and return to the original city ？”

This is one of combinatorial optimization NP problem , It is very important in operations research and theoretical computer science .

In this question , Please find the path closest to the solution of the traveling salesman problem from the given path list .

Input format
The first line contains two integers N and M, Respectively represent the number of cities and Undirected graph The number of middle edges .

Next M That's ok , Every line is marked with City1 City2 Dist Format describes an edge , The city number is from 1 To N,Dist Positive and no more than 100.

The next line contains an integer K, Indicates the number of given paths .

Next K Line description path , The format is ：

n C1 C2 … Cn
n Indicates the number of cities that a given path passes through ,Ci Is the number of the city in the path .

Output format
For each path , Output in one line Path X: TotalDist (Description).

among X Is the path number （ from 1 Start ）,TotalDist Indicates the total distance of the path （ If the distance does not exist , The output NA）,Description Is one of the following ：

TS simple cycle, If this is a simple loop to visit every city .
TS cycle, If this is a loop to visit every city , But it's not a simple circuit .
Not a TS cycle, If this is not a circuit that visits every city .
The last line , Output Shortest Dist(X) = TotalDist,X It is the circuit number closest to the solution of the traveling salesman problem ,TotalDist Is its total distance .

There is guaranteed to be a unique solution .

Data range
2<N≤200,
N−1≤M≤N(N−1)2,
1≤K≤1000,
1≤n≤300
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

My solution ：

#include <bits/stdc++.h>
using namespace std;
const int N = 210, INF = 0x3f3f3f3f;
int n, m, k;
int d[N][N], vi[310];
bool st[N];
int main(){
    int min_dist = INF;
    int min_id;
    cin >> n >> m;
    memset(d, 0x3f, sizeof d);
    for(int i = 0; i < m; i ++ ){
        int a, b, c;
        cin >> a >> b >> c;
        d[a][b] = d[b][a] = c; 
    }
    cin >> k;
    for(int T = 1; T <= k; T ++ ){
        int sum = 0;
        bool success = true;
        int v;
        cin >> v;
        memset(st, 0, sizeof st);
        for(int i = 1; i <= v; i ++ ) cin >> vi[i];
        for(int i = 1; i + 1 <= v; i ++ ){
            int a = vi[i], b = vi[i + 1];
            if(d[a][b] == INF){
                sum = -1;
                success = false;
                break;
            }
            else{
                st[a] = true;
                sum += d[a][b];
            }
        }
        for(int i = 1; i <= n; i ++ ){
            if(!st[i]){
                success = false;
                break;
            }
        }
        if (vi[1] != vi[v]) success = false;
        
        if(sum == -1){
            printf("Path %d: NA (Not a TS cycle)\n", T);
        } 
        else{
            if(!success){
                printf("Path %d: %d (Not a TS cycle)\n", T, sum);
            }
            else{
                if(v == n + 1) printf("Path %d: %d (TS simple cycle)\n", T, sum);
                else printf("Path %d: %d (TS cycle)\n", T, sum);
                if(sum < min_dist){
                    min_dist = sum;
                    min_id = T;
                }
            }
        }
    }
    printf("Shortest Dist(%d) = %d\n", min_id, min_dist);
    return 0;
}