题目描述

判断哈密尔顿回路：经过所有点的简单回路
（1）如果没有没有边通过INF标记不可达
（2）如果没有经过所有的节点||不是回路path[0]!=path[k-1]||或者存在边不可达   (Not a TS cycle)
（3）否则  如果k==n+1  说明是简单回路  (TS simple cycle)   取最小路径
（4）否则 即k!=(n+1)是一个回路 所有边可达 经过所有节点  输出只是一个环 (TS cycle) 取最小路径

算法1

C++ 代码

#include<iostream>
#include<cstring>
using namespace std;
const int INF=0x3f3f3f;
const int N=210;
const int K=1010;
int g[N][N];
int st[N];
int path[N*2];
int n,m;
int dist[K],TotalDist=INF;
int e=1;

void check(int r,int k){//表示第r次询问序列长度为k
    memset(st,0,sizeof(st));
    int res=0;//距离累加

    for(int i=0;i<k-1;i++){
        st[path[i]]=1;
        if(!g[path[i]][path[i+1]]){
            res=INF;//没有距离
            break;
        }else{
            res+=g[path[i]][path[i+1]];
        }
    }
    bool flag=true;//标记是否访问所有节点
    for(int i=1;i<=n;i++){
        if(!st[i]){
            flag=false;
            break;
        }
    }

    // cout<<"res="<<res<<endl;

    if(!flag||path[0]!=path[k-1]||res==INF){   //如果不是回路或者没有访问所有的节点   Not a TS cycle
        if(res==INF){
            cout<<"Path "<<r<<": "<<"NA"<<" (Not a TS cycle)"<<endl;
        }else{
            cout<<"Path "<<r<<": "<<res<<" (Not a TS cycle)"<<endl;
        }
    }else if(k==(n+1)){  //访问了所有的节点，并且序列长度为n+1,说明是访问所有节点的简单回路
        cout<<"Path "<<r<<": "<<res<<" (TS simple cycle)"<<endl;
        if(TotalDist>res){
            TotalDist=res;
            e=r;
        }
    }else{
        //说明TS cycle
        cout<<"Path "<<r<<": "<<res<<" (TS cycle)"<<endl;
        if(TotalDist>res){
            TotalDist=res;
            e=r;
        }
    }

}

int main(){
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int a,b,c;
        cin>>a>>b>>c;
        g[a][b]=g[b][a]=c;
    }

    int q;cin>>q;
    for(int i=1;i<=q;i++){
        memset(path,0,sizeof(path));
        int k;cin>>k;
        for(int j=0;j<k;j++){
            cin>>path[j];
        }

        check(i,k);

    }
    cout<<"Shortest Dist("<<e<<") = "<<TotalDist<<endl;

    return 0;
}