PAT 1150 Travelling Salesman Problem（25 分）

最新推荐文章于 2021-01-17 16:15:42 发布

cillyb

最新推荐文章于 2021-01-17 16:15:42 发布

阅读量641

点赞数 1

分类专栏：水题文章标签： PAT

本文链接：https://blog.csdn.net/CillyB/article/details/82558145

版权

水题专栏收录该内容

20 篇文章

订阅专栏

题意：给你n个点，m条边，现在给你k条路径，问你每条路径分别属于什么。

TS simple cycle if it is a simple cycle that visits every city;
TS cycle if it is a cycle that visits every city, but not a simple cycle;
Not a TS cycle if it is NOT a cycle that visits every city

思路：首先for一遍路径记录距离和，顺便看下路径是否连通。看一下一共访问过几个城市，如果不是n个城市或者首尾不同，那就是Not a TS cycle，如果路径的城市数为n+1，则是TS simple cycle，否则是TS cycle。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int maxn = 1e3+5;
const int INF = 0x3f3f3f3f;
int dis[maxn][maxn];
int a[maxn];
bool vis[maxn];

int main(void)
{
    int n, m, k;
    while(cin >> n >> m)
    {
        memset(dis, -1, sizeof(dis));
        for(int i = 0; i < m; i++)
        {
            int u, v, w;
            scanf("%d%d%d", &u, &v, &w);
            if(dis[u][v] == -1) dis[u][v] = w;
            else dis[u][v] = min(dis[u][v], w);
            if(dis[v][u] == -1) dis[v][u] = w;
            else dis[v][u] = min(dis[v][u], w);
        }
        scanf("%d", &k);
        int ansID, ans = INF;
        for(int ca = 1; ca <= k; ca++)
        {
            int num;
            scanf("%d", &num);
            memset(vis, 0, sizeof(vis));
            int visNum = 0;
            for(int i = 1; i <= num; i++)
            {
                scanf("%d", &a[i]);
                if(vis[a[i]] == 0)
                {
                    vis[a[i]] = 1;
                    visNum++;
                }
            }
            int x = 0, cur = 1;
            for(int i = 1; i < num; i++)
            {
                int w = dis[a[i]][a[i+1]];
                if(w == -1)
                {
                    cur = 0;
                    break;
                }
                else x += w;
            }
            if(cur == 0) printf("Path %d: NA (Not a TS cycle)\n", ca);
            else
            {
                if(visNum == n && a[1] == a[num])
                {
                    if(num == n+1) printf("Path %d: %d (TS simple cycle)\n", ca, x);
                    else printf("Path %d: %d (TS cycle)\n", ca, x);

                    if(x < ans) ans = x, ansID = ca;
                }
                else printf("Path %d: %d (Not a TS cycle)\n", ca, x);
            }
        }
        printf("Shortest Dist(%d) = %d\n", ansID, ans);
    }
    return 0;
}