题目粗心：

给定一个N个顶点和M条边的无向图,K个查问，每一个查问输出长度为n的门路，判断该门路是否是TS cycle或者TS simple cycle并输入题目要求的对应信息。

算法思路：

咱们应用邻接矩阵G保留该图的边权，而后应用path数组保留每一次查问的门路，判断该门路是否是TS cycle和TS simple cycle的办法如下：

  • 1、应用 set differentVertices汇合保留所有门路上的不同顶点数目，total_dist为门路长度，frequencyOfStart为终点呈现的次数，isNa标记门路是否连通。
  • 2、遍历门路上每一个顶点，累加total_dist的边权并判断以后边权是否为0，如果是，阐明该门路不连通，isNa = true，并统计终点呈现的次数。
  • 3、首先判断isNa是否为true，如果是阐明以后门路不连通，肯定不是cycle，输入printf("Path %d: NA (Not a TS cycle)n",i);如果不是转4
  • 4、判断终点和起点是否一样，如果不一样，阐明该门路不是cycle，输入printf("Path %d: %d (Not a TS cycle)n",i,total_dist);否则转5
  • 5、判断differentVertices的大小(门路中呈现的不同顶点数目)是否等于N，如果不是，阐明没有拜访每一个城市,不是TS cycle或者TS simple cycle，输入printf("Path %d: %d (Not a TS cycle)n",i,total_dist);否则转6
  • 6、判断顶点呈现了几次，如果是2次，阐明是TS simple cycle，输入printf("Path %d: %d (TS simple cycle)n",i,total_dist);否则是TS cycle,输入printf("Path %d: %d (TS cycle)n",i,total_dist);同时在此状况下，得更新TS cycle或者TS simple cycle的最小门路长度和编号。

留神点：

  • 1、只有在判断以后门路是TS cycle或者TS simple cycle的时候能力进行更新最小门路长度

提交后果：

AC代码：

#include<cstdio>#include<vector>#include<unordered_set>using namespace std;int N,M;// 顶点数目和边数int G[205][205];// 邻接矩阵,存储边权，不存在为0int main(){    scanf("%d %d",&N,&M);    int a,b,dist;    for (int i = 0; i < M; ++i) {        scanf("%d %d %d", &a, &b, &dist);        G[a][b] = G[b][a] = dist;    }    int K,num,city;    scanf("%d",&K);    int min_dis = 0x3fffffff;    int min_dis_index = -1;    for(int i=1;i<=K;++i){        scanf("%d",&num);        vector<int> path;        unordered_set<int> differentVertices;// 门路中不同顶点的数目        for (int j = 0; j < num; ++j) {            scanf("%d",&city);            path.push_back(city);        }        // 取得门路长度和终点呈现的次数        int total_dist = 0;        int frequencyOfStart = 0;        bool isNa = false;        for (int k = 0; k < path.size(); ++k) {            differentVertices.insert(path[k]);            if(k<path.size()-1){                total_dist += G[path[k]][path[k+1]];                if(G[path[k]][path[k+1]]==0) {                    // 存在无奈达到的边                    isNa = true;                }            }            if(path[k]==path[0]){                ++frequencyOfStart;            }        }        if(isNa){            // 以后门路不连通，肯定不是cycle            printf("Path %d: NA (Not a TS cycle)\n",i);        } else {            // 肯定连通            if(path[0]!=path[path.size()-1]){                // 终点和起点不一样，不是cycle                printf("Path %d: %d (Not a TS cycle)\n",i,total_dist);            } else {                // 肯定是cycle，终点至多呈现了2次                if(differentVertices.size()!=N){                    // 没有拜访每一个城市,不是TS cycle或者TS simple cycle                    printf("Path %d: %d (Not a TS cycle)\n",i,total_dist);                } else {                    // 肯定是TS cycle或者TS simple cycle                    if(min_dis>total_dist){                        // 更新最短距离和编号                        min_dis_index = i;                        min_dis = total_dist;                    }                    if(frequencyOfStart==2){                        // 顶点只呈现了2次且拜访了每一个城市,是TS simple cycle                        printf("Path %d: %d (TS simple cycle)\n",i,total_dist);                    } else{                        // 顶点呈现大于2次且拜访了每一个城市,是TS cycle                        printf("Path %d: %d (TS cycle)\n",i,total_dist);                    }                }            }        }    }    printf("Shortest Dist(%d) = %d",min_dis_index,min_dis);    return 0;}