Travelling Salesman Problem

#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<cstdio>
#include<sstream>
#include<set>
#include<map>
#include<cmath>
#include<vector>
#include<unordered_map>
using namespace std;
int n,m;
const int maxn=202;
const int maxm=40004;
const int INF=0X3F3F3F3F;
struct Edge{
    int to;
    int cost;
    int next;
};
int city[maxn][maxn];
int main(){
    cin>>n>>m;
    memset(city,INF,sizeof(city));
    for(int i=0;i<m;i++){
        int city1,city2,dist;
        cin>>city1>>city2>>dist;
        city[city1][city2]=dist;
        city[city2][city1]=dist;
        city[city1][city1]=0;
        city[city2][city2]=0;
    }
    int k;
    cin>>k;
    int mins=INF;
    int minj=1;
    for(int j=1;j<=k;j++){
        int num;
        cin>>num;
        int num2=num;
        int ans=0;
        int start=0,endss;
        map<int,int>ma;
        int tot=0;//记录总共遍历了几个结点
        int type=0;//0-simple,1-cycle,2-not
        int path=0;
        int pre=0;
        while(num2--){
            int c;
            cin>>c;
            if(ans==0){
                start=c;
                ma[c]++;
                pre=start;
                tot++;
            }else{
                if(ma[c]!=0){
                    if((num2!=0)||(num2==0&&start!=c)){
                        type=1;//非简单环
//                        cout<<num2<<" "<<c<<endl;
                    }
                }else{
                    tot++;
                    ma[c]++;
                }
                path+=city[pre][c];
                pre=c;
            }
            ans++;
            if(ans==num)
                endss=c;
        }
        if(path>=INF){
            cout<<"Path "<<j<<": NA (Not a TS cycle)"<<endl;
        }else{
            if(tot!=n){
                cout<<"Path "<<j<<": "<<path<<" (Not a TS cycle)"<<endl;
            }else{
                if(start!=endss){
                    cout<<"Path "<<j<<": "<<path<<" (Not a TS cycle)"<<endl;
                    continue;
                }
                if(type==1){
                    cout<<"Path "<<j<<": "<<path<<" (TS cycle)"<<endl;
                }else{
                    cout<<"Path "<<j<<": "<<path<<" (TS simple cycle)"<<endl;
                }
                if(path<mins){
                    mins=path;
                    minj=j;
                }
            }
        }
    }
    cout<<"Shortest Dist("<<minj<<") = "<<mins<<endl;
    return 0;
}复制