共计 2312 个字符,预计需要花费 6 分钟才能阅读完成。
题目粗心:
给定一个 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];// 邻接矩阵, 存储边权,不存在为 0
int 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;
}
正文完