本意不是叫你求最短哈密顿图，是给你一条路径叫你判断是不是哈密顿图，如果不是，有没有遍历所有点。如果没有遍历所有的点，有没有保持基本的连贯性？
#include<iostream>
#include<string>
#include<string.h>
#include<algorithm>
#include<vector>
#include<map>
#include<cstdlib>
#include <unordered_map>
using namespace std;
typedef long long LL;
#define N 201
int d[N][N]={0};
// 记录边的权值，因为边数少于200*200所以问题不大
int main(){
int shortest_node=0,shortest_length=1000000;
// shortest_node 是对应的最优点，shortest_length是对应的最小长度。
int points,edges,i,j;
// points 点数，edges 边数
cin>>points>>edges;
int p1,p2,value;
for(i=0;i<edges;i++){
cin>>p1>>p2>>value;
d[p1][p2]=value;
d[p2][p1]=value;
// 初始化边的权值数组
}
int counts=0,circle=0,input;
cin>>counts;
for(i=0;i<counts;i++){
int length=0;
cin>>circle;
unordered_map<int,int>m;
// 利用map统计点出现的次数，如果出现超过两次，可以认为有问题。
int pre=0;
bool isnull=false;
// 判断是不是合法的路径（中间没断掉）
bool issimple=true;
// 判断是不是简单图 simple TS cycle
cin>>input;
// 第一个不用统计，因为终点就是起点。
// m[input]++;
pre=input;
for(j=1;j<circle;j++){
cin>>input;
m[input]++;
if(d[pre][input]==0){
isnull=true;
// Path不合法
}
else{
length+=d[pre][input];
// Path合法，计算Path长度
}
pre=input;
}
if(m.size()==points&&!isnull){
for(auto it:m){
if(it.second>1){
issimple=false;
// 不是简单图
break;
}
}
if(issimple){
printf("Path %d: %d (TS simple cycle)\n",i+1,length);
}
else{
printf("Path %d: %d (TS cycle)\n",i+1,length);
}
}
else{
// Not a TS cycle，Path置为最大值
if(isnull){
printf("Path %d: NA (Not a TS cycle)\n",i+1);
}
else{
printf("Path %d: %d (Not a TS cycle)\n",i+1,length);
}
length=1000000;
}
if(length<shortest_length&&m.size()==points){
shortest_length=length;
shortest_node=i+1;
}
}
if(shortest_length==1000000){
// 如果所有测试数据都NA，那么输出NA
printf("Shortest Dist(%d) = NA",shortest_node);
}else{
printf("Shortest Dist(%d) = %d",shortest_node,shortest_length);
}
}
/*
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
*/
