文章目錄

• • 題目分析
  • 題目鏈接

題目分析

來源：acwing
分析：
旅行商問題：訪問每個城市并回到原城市的最短路。

思路: 1）判斷相鄰兩點有無距離（NA）；2）每個點是否都能到；3）是否是回路；4）是否是簡單回路。

ac代碼

#include<bits/stdc++.h> using namespace std; const int N = 310,INF = 0x3f3f3f3f;int n, m; int d[N][N],vers[N]; bool st[N]; int main(){memset(d ,0x3f ,sizeof d);cin >> n >>m ;for(int i= 0; i< m; i++){int a, b,c;cin >> a >> b >> c;d[a][b] = d[b][a] = c;}int k;cin >> k;int min_dist =INF,min_id;//按照編號來讀for(int T = 1; T <=k;T++){int cnt;cin >> cnt;//讀入序列for(int i = 0; i< cnt; i++) cin>> vers[i];int sum = 0; //總長度bool success =true; //記錄是否存在距離memset(st, 0 ,sizeof st);//對于相鄰的兩個點，如果沒有邊，則沒有距離NAfor(int i = 0; i+ 1 < cnt ; i++) {int a = vers[i] , b =vers[i+1];if(d[a][b] >= INF){//沒有邊sum = -1;success =false;break;}else sum += d[a][b];st[a] = true; //遍歷過，標記一下}//對于所有點，看是否都遍歷過，即是否包含所有的點for(int i = 1; i<= n; i++){if(!st[i]){success = false;break;}}//不是回路if(vers[0] != vers[cnt-1]) success =false;if(sum == -1) printf("Path %d: NA (Not a TS cycle)\n",T);else{//不是回路if(!success) printf("Path %d: %d (Not a TS cycle)\n", T, sum);else{//僅僅包含n+1個點，簡單回路if(cnt == n+1) printf("Path %d: %d (TS simple cycle)\n",T,sum);else printf("Path %d: %d (TS cycle)\n",T,sum);if(sum < min_dist) min_dist = sum,min_id =T;}}}printf("Shortest Dist(%d) = %d",min_id,min_dist);}

題目鏈接

PAT甲級1150 Travelling Salesman Problem
https://www.acwing.com/problem/content/1645/

總結

以上是生活随笔為你收集整理的PAT甲级1150 Travelling Salesman Problem：[C++题解]旅行商问题、图论的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。