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;
}