1150 Travelling Salesman Problem(52行代码+超详细注解)

news/2025/2/14 16:07:53/

分数 25

全屏浏览题目

作者 CHEN, Yue

单位 浙江大学

The "travelling salesman problem" asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city and returns to the origin city?" It is an NP-hard problem in combinatorial optimization, important in operations research and theoretical computer science. (Quoted from "https://en.wikipedia.org/wiki/Travelling_salesman_problem".)

In this problem, you are supposed to find, from a given list of cycles, the one that is the closest to the solution of a travelling salesman problem.

Input Specification:

Each input file contains one test case. For each case, the first line contains 2 positive integers N (2<N≤200), the number of cities, and M, the number of edges in an undirected graph. Then M lines follow, each describes an edge in the format City1 City2 Dist, where the cities are numbered from 1 to N and the distance Dist is positive and is no more than 100. The next line gives a positive integer K which is the number of paths, followed by K lines of paths, each in the format:

n C1​ C2​ ... Cn​

where n is the number of cities in the list, and Ci​'s are the cities on a path.

Output Specification:

For each path, print in a line Path X: TotalDist (Description) where X is the index (starting from 1) of that path, TotalDist its total distance (if this distance does not exist, output NA instead), and Description is one of the following:

  • 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.

Finally print in a line Shortest Dist(X) = TotalDist where X is the index of the cycle that is the closest to the solution of a travelling salesman problem, and TotalDist is its total distance. It is guaranteed that such a solution is unique.

Sample Input:

6 10
6 2 1
3 4 1
1 5 1
2 5 1
3 1 8
4 1 6
1 6 1
6 3 1
1 2 1
4 5 1
7
7 5 1 4 3 6 2 5
7 6 1 3 4 5 2 6
6 5 1 4 3 6 2
9 6 2 1 6 3 4 5 2 6
4 1 2 5 1
7 6 1 2 5 4 3 1
7 6 3 2 5 4 1 6

Sample Output:

Path 1: 11 (TS simple cycle)
Path 2: 13 (TS simple cycle)
Path 3: 10 (Not a TS cycle)
Path 4: 8 (TS cycle)
Path 5: 3 (Not a TS cycle)
Path 6: 13 (Not a TS cycle)
Path 7: NA (Not a TS cycle)
Shortest Dist(4) = 8

代码长度限制

16 KB

时间限制

250 ms

内存限制

64 MB

#include<bits/stdc++.h>
using namespace std;
const int N=209,INF=0x3f3f3f3f;
int n,m; 
int g[N][N];
int minid,mindist=INF;//记录最小的回路编号和距离 
int main(){
    cin>>n>>m;
    memset(g,0x3f,sizeof g);//初始化距离为无穷大 
    for(int i=0;i<m;i++){
        int a,b,d;
        cin>>a>>b>>d;
        g[a][b]=g[b][a]=d;
    }
    int k;
    cin>>k;
    for(int i=1;i<=k;i++){//k个路径
        int num;
        cin>>num;//路径的结点个数 
        vector<int>v;
        for(int j=0;j<num;j++){
            int node;
            cin>>node;
            v.push_back(node);//结点插入数组 
        }
        int total=0,flag=1;//分别表示总距离和是否是访问过所有结点的环 
        bool st[N]={0};//用来记录访问过的结点 
        for(int j=1;j<num;j++){
            int a=v[j-1],b=v[j];
            st[a]=true,st[b]=true;
            if(g[a][b]==INF){//若邻接结点没有边 
                total=-1;//距离置为-1 
                break;
            }
            else total+=g[a][b];
        }
        if(v[0]!=v[num-1])flag=0;//若起点和终点不等则不是环 
        for(int i=1;i<=n;i++)if(!st[i])flag=0;//若有访问所有节点flag置0 
        if(total==-1)printf("Path %d: NA (Not a TS cycle)\n",i);//若不连通 
        else{//若连通了 
            if(flag){//若是访问过所有结点的环 
                if(total<mindist)mindist=total,minid=i;//更新路径编号和距离 
                if(num==n+1)printf("Path %d: %d (TS simple cycle)\n",i,total);//结点数为n+1则是简单回路 
                else if(num>n+1)printf("Path %d: %d (TS cycle)\n",i,total);//大于n+1则不是简单回路 
            }
            else printf("Path %d: %d (Not a TS cycle)\n",i,total);//若不是访问过所有结点的环
        }
        
    }
    printf("Shortest Dist(%d) = %d\n",minid,mindist);//输出最小距离回路的编号和距离 
    return 0;
}


http://www.ppmy.cn/news/75191.html

相关文章

【计算机系统基础3】数据的存储与运算

【计算机系统基础3】数据的存储与运算 3.程序调试与实践&#xff1a;数据存储与运算3.1真值与机器数3.1.1整数的编码 3.2数据的存储3.3数组的对齐3.4数据类型的转换3.4.1整数之间的数据类型转换3.4.2整数与浮点数之间的转换3.4.3自动类型转换 3.5浮点数的表示和运算--IEEE 7543…

不要做一个透明人:展现真实的自己

✨求关注~ &#x1f600;博客&#xff1a;www.protaos.com 目录&#xff1a; 引言&#xff1a;透明人的困境透明人的定义与特征 2.1 透明人的追求与代价 2.2 社交媒体与透明人现象的关系透明度的局限性 3.1 自我保护与隐私权 3.2 虚假的透明度和个人形象管理重建真实的自我 4.…

QT窗体绘图QPainter

QPainter INSCODE AI 创作助手&#xff1a; QPainter是Qt中的一个类&#xff0c;用于在窗口、图像或其他用户界面上绘制图形和文本。它提供了一些方便的方法来画线、矩形、圆、多边形和文本 QPainter绘图函数 INSCODE AI 创作助手&#xff1a; QPainter是Qt中一个用于绘图的类&…

Vs+Qt+C++电梯调度控制系统

程序示例精选 VsQtC电梯调度控制系统 如需安装运行环境或远程调试&#xff0c;见文章底部个人QQ名片&#xff0c;由专业技术人员远程协助&#xff01; 前言 这篇博客针对<<VsQtC电梯调度控制系统>>编写代码&#xff0c;代码整洁&#xff0c;规则&#xff0c;易读。…

第二章 逻辑分类模型

目录 一、逻辑回归基本模型二、处理多维特征输入三、加载数据集四、多分类问题 一、逻辑回归基本模型 基本模型&#xff1a; y ^ σ ( x ∗ ω b ) \hat{y} \sigma (x * \omega b) y^​σ(x∗ωb)&#xff0c;其中 σ ( ) \sigma() σ() 表示 sigmod 函数 σ ( x ) 1 1…

已解决python使用pymysql向mysql数据库插入数据报错pymysql.err.DataError: (1366, ‘‘)

已解决&#xff0c;在python代码是使用pymysql向mysql数据库插入数据时报错pymysql.err.DataError: (1366, ) 问题描述 我从某个网页上抓取并解析了一段html代码&#xff0c;然后将html代码转为utf-8格式&#xff0c;之后将html代码作为数据表的一个属性存入mysql数据库中&…

第三十八章 梦中接龙

回到地下一层&#xff0c;不忍和尚仍保持着刚才的姿势&#xff0c;面前却多了一套僧袍。 “来&#xff0c;试试。”没等巴哥奔念诵‘阿弥陀佛’四字诀&#xff0c;不忍抢先发出心电。 耐不住好奇&#xff0c;巴哥奔拾起僧衣轻轻一抖。 藕丝般黏稠的褐色连体长睡衣瞬间将她的手掌…

python+django音乐推荐网站vue

为此开发了本音乐推介网站 &#xff0c;为用户提供一个基于音乐推介网站&#xff0c;同时方便管理员&#xff1b;首页、个人中心、用户管理&#xff0c;类型信息管理、乐器类型管理、歌曲信息管理、戏曲信息管理、MV专区管理、付费音乐管理、订单信息管理、音乐文件管理、论坛管…