[C++知识库]1150 Travelling Salesman Problem (25 分)

题目大意:给一个无向图和一些路径，判断路径是否为环，且环分为简单环和旅行商环。

如果一个路径经过所有点，其头尾点相等，那么他就是一个环，在这个环上除去源点都只走过一次，(源点两次)那么就是简单环，否则就是旅行商环。

如果两个点之间没有连接，那么就不存在环。

#include <iostream>
#include <cstring>
#include <queue>
#include <unordered_map>
using namespace std;
const int N = 310;
int n,m,k,ans = 1e9,dis,s;
int g[N][N];
void solve(vector<int> &p,int j)
{   
    unordered_map<int,int>mp;
    int a = p[0],b,f1 = 0,f2 = 0,f3 = 1; 
    dis = 0;
    for(int i = 1; i < p.size(); i ++ )
    {
        b = p[i];mp[b] ++;
        if(mp[b] > 1) f2 = 1;//中间是否出现环
        if(g[a][b] == 0x3f3f3f3f) //如果不相连
        {
            f1 = 1;break;
        }
        dis += g[a][b], a = b;
    }
    if(mp.size() != n) f3 = 0; //判断是否包含所有点
    if(f1 == 1) printf("NA (Not a TS cycle)\n");
    else {
        if(f2 == 1 && f3 == 1 && p[0] == p.back()) printf("%d (TS cycle)\n",dis);
        else if (f2 == 0 && f3 == 1 && p[0] == p.back()) printf("%d (TS simple cycle)\n",dis);
        else  printf("%d (Not a TS cycle)\n",dis);
        if(ans > dis && f3 == 1) ans = dis,s = j;
    }
}
int main()
{
    memset(g,0x3f,sizeof g);
    cin >> n >> m;
    for(int i = 0; i < m; i ++)
    {
        int a,b,c;
        cin >> a >> b >> c;
        g[a][b] = g[b][a] = min(g[a][b],c);//习惯，怕题目有重边
    }
    cin >> k;
    for(int j = 1; j <= k; j ++)
    {
        int x;
        cin >> x;
        vector<int>p(x);
        for(int i = 0; i < x; i ++) cin >> p[i];  
        printf("Path %d: ",j);solve(p,j);
    }
    printf("Shortest Dist(%d) = %d",s,ans);
    return 0;
}