PAT A1150 Travelling Salesman Problem(C++)

发表于 | 分类于 | |
字数统计: 540 字 | 阅读时长 ≈ 3 分钟
PAT甲级目录 | PAT乙级目录

题目描述

原题地址：A1150 Travelling Salesman Problem

解题思路

  • 用一个二维数组存储两个城市间的距离，如不存在这样的边，则距离为 0.
  • 遍历每条路径，判断是否存在这样的边，如果存在，累加距离，同时更新城市访问次数。如果不存在，则修改标记另 flag = -1，表示不构成一个 cycle 并且无法计算距离。
  • 判断路径的首尾城市是否一致，不一致则不能构成 cycle，修改对应标记。
  • 遍历访问数组，根据所有城市是否只访问一次，判断是否为 simple TS cycle ，修改对应标记。
  • 更新最短路径距离以及对应路径序号。

易错点：

  • 因为起点和终点是同一个城市，对应计数值会多 1，因此需要修正。

也许陌生的知识点

  • vector<int> path(p);
    • 创建了一个指定长度为 p 的数组。
    • 所需头文件：vector

代码示例：

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
#include <cstdio>
#include <vector>
using namespace std;
int main(){
  int N, M, K, G[202][202] = {{0}};
  scanf("%d %d", &N, &M);
  for(int i = 0; i < M; i++){
    int c1, c2, d;
    scanf("%d %d %d", &c1, &c2, &d);
    G[c1][c2] = d;
    G[c2][c1] = d;
  }
  scanf("%d", &K);
  int min_id = -1, min_dis = -1;
  for(int i = 1; i <= K; i++){
    int p, vis[202] = {0}, total = 0, flag = 1;
    scanf("%d", &p);
    vector<int> path(p);
    for(int j = 0; j < p; j++){
      scanf("%d", &path[j]);
      vis[path[j]]++;
      if(j != 0) {
        if(G[path[j]][path[j-1]] == 0) flag = -1;// not a cycle
        else total += G[path[j]][path[j-1]];
      }
      if(j == p-1 && flag > 0){
        if(path[j] != path[0]) flag = -2;// not a cycle
        else vis[path[j]]--;
      }
    }
    for(int j = 1; flag > 0 && j <= N; j++){
      if(vis[j] == 0) flag = -2;// not TS cycle
      if(vis[j] > 1) flag = 2; // TS cycle
    }
    printf("Path %d: ", i);
    if(flag == 1) printf("%d (TS simple cycle)\n", total);
    else if(flag == 2) printf("%d (TS cycle)\n", total);
    else if(flag == -2) printf("%d (Not a TS cycle)\n", total);
    else if(flag == -1) printf("NA (Not a TS cycle)\n");
    if(min_dis == -1 || (flag > 0 && min_dis > total)){
      min_dis = total;
      min_id = i;
    }
  }
  printf("Shortest Dist(%d) = %d\n", min_id, min_dis);
  return 0;
}