[数据结构与算法]1150 Travelling Salesman Problem

1150 Travelling Salesman Problem

题目大意

给出一条路径，判断这条路径是不是这个图的旅行商环路、简单旅行商环路和非旅行商环路。

基本思路

如果给出的路径存在某两个连续的点不可达第一个结点和最后一个结点不同或者这个路径没有访问过图中所有的点，那么它就不是一个旅行商环路。如果满足了旅行商环路的条件，那么再判断这个旅行商环路是否是简单旅行商环路，即是否访问过n+1个结点并且源点访问两次。最后输出这些旅行商环路中经过的路径最短的路径编号和路径长度。

代码

具体数据结构和相似思路请看代码

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
const int MAXN=210;
const int INF=100000000;

int n,m,k;
int G[MAXN][MAXN];

int main(){
    cin>>n>>m;
    fill(G[0], G[0] + MAXN * MAXN, INF);
    for(int i=0;i<m;i++){
        int v1,v2,dis;
        cin>>v1>>v2>>dis;
        G[v1][v2]=G[v2][v1]=dis;
    }
    int mindis=INF,pathindex=-1;//所有旅行商环路中的总路径的最小值及其路径编号
    int cnt = 1;//记录路径编号
    cin>>k;
    for(int i=0;i<k;i++){
        int num;
        cin>>num;
        vector<int> v;
        set<int> s;
        for (int j = 0; j < num;j++){
            int ans;
            cin>>ans;
            v.push_back(ans);
            s.insert(ans);
        }
        //判断该图是否是一个旅行商环路。初始化为是旅行商环路
        int flag = 1;
        if(s.size()<n||v[0]!=v[num-1]){//该路径不是旅行商环路1(路径不含所有顶点 或者 首尾顶点不一致)
            flag = 0;
        }
        int dis=0;//累加本次路径长度
        for (int i = 0; i < num-1 ;i++){//该路径不是旅行商环路2(连续两个顶点之间不存在边)
            int id1 = v[i], id2 = v[i + 1];
            dis += G[id1][id2];
            if(G[id1][id2]==INF){
                flag = 0;
                dis=-1;
                break;
            }
        }
        //判断出该路径不是一个旅行商环路
        if(!flag){
            if(dis==-1){
                cout << "Path " << cnt++ << ": "<<"NA"
                 << " (Not a TS cycle)" << endl;
                continue;
            }else{
                cout << "Path " << cnt++ << ": "<<dis
                 << " (Not a TS cycle)" << endl;
                continue;
            }
        }
        //判断该路径是不是简单旅行商路径
        if(v[0]==v[num-1]&&v.size()==n+1){
            cout << "Path " << cnt++ << ": "<<dis
                 << " (TS simple cycle)" << endl;
        }else{
            cout << "Path " << cnt++ << ": "<<dis
                 << " (TS cycle)" << endl;
        }
        //如果当前路径是旅行商路径并且值小于所有旅行商路径中总路径的最小值mindis
        //更新所有旅行商路径中总路径的最小值mindis及其路径编号pathindex
        if(dis<mindis){
                mindis = dis;
                pathindex = cnt - 1;
        }
    }
    printf("Shortest Dist(%d) = %d", pathindex, mindis);
}