Home PAT 1150 Travelling Salesman Problem
Post
Cancel

PAT 1150 Travelling Salesman Problem

Link

简单分析一下这个逻辑:

  • TS simple cycle: 是环 (因此也就是连通的)、是简单的、是 TS 的
  • TS cycle: 是环 (因此也就是连通的)、不是简单的、是 TS 的
  • Not a TS cycle:
    • 可计算出路径: 是连通的
    • 不可计算出路径: 不是连通的
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <string.h>
#include <vector>
using namespace std;
int n,m,k,num,minv=0x3f3f3f3f,minIndex;
int dis[210][210],c[210];
bool v[210];
int main() {
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i){
        int c1,c2;
        scanf("%d%d",&c1,&c2);
        scanf("%d",&dis[c1][c2]);
        dis[c2][c1]=dis[c1][c2];
    }
    scanf("%d",&k);
    for(int id=1;id<=k;++id){
        memset(v,false,sizeof(v));
        bool isSimple=true,isCycle=true,isConnected=true,isTS=true;
        scanf("%d",&num);
        for(int j=1;j<=num;++j)
            scanf("%d",&c[j]);
        //是否是简单的(路径中每个城市只出现一次)
        for(int j=1;j<num;++j){
            if(v[c[j]]) isSimple=false;
            else v[c[j]]=true;
        }
        //是否是TS的(n个城市每个城市都要经过)
        for(int j=1;j<=n;++j)
            if(!v[j]){
                isTS=false;
                break;
            }
        //是否是环
        if(c[num]!=c[1]) isCycle=false;
        int cur=0;
        for(int j=2;j<=num;++j){
            if(!dis[c[j]][c[j-1]]){//路径是否是连通的
                isCycle=isConnected=false;//都不连通了肯定也就不是环了,并且总长度也不能计算
                break;
            }else cur+=dis[c[j]][c[j-1]];
        }
        if(isConnected&&isCycle&&isTS&&cur<minv){//只有是连通的TS环(不一定是简单的)才能更新minv
            minv=cur;
            minIndex=id;
        }
        printf("Path %d: ",id);
        if(isCycle&&isSimple&&isConnected&&isTS) printf("%d (TS simple cycle)\n",cur);
        else if(isCycle&&!isSimple&&isConnected&&isTS) printf("%d (TS cycle)\n",cur);
        else if(isConnected) printf("%d (Not a TS cycle)\n",cur);
        else printf("NA (Not a TS cycle)\n");
    }
    printf("Shortest Dist(%d) = %d\n",minIndex,minv);
    return 0;
}
This post is licensed under CC BY 4.0 by the author.