PAT甲级 1150 Travelling Salesman Problem (25 分)

\quad这个题意思是给你一张图,再给你若干组点的组合,让你判断这些点的组合是否满足旅行商问题:即从第一个点出发,遍历完所有顶点再回到原点。

  • pathLen记录每条路长度。若相邻两点不连接则长度为INF
  • vis记录是否所有的顶点都被访问过

\quad三种情况,如下

  • 若初始点与最后一个点相同,且遍历完所有点,且定点之间均有边连接,且刚好只有n+1个点,这种情况下是“(TS simple cycle)”
  • 若初始点与最后一个点相同,且遍历完所有点,且定点之间均有边连接,但不止n+1个点或者少于n+1个点,这种情况知识一个圈,输出"(TS cycle)"
  • 其他情况下输出“(Not a TS cycle)”即可

\quad程序如下:

#include <bits/stdc++.h>
using namespace std;

const int maxn = 201;
int dis[maxn][maxn];
int vis[maxn];
const int INF = 0x3f3f3f3f;
int main(int argc, char const *argv[])
{
	ios::sync_with_stdio(false);
	int n, m;
	cin >> n >> m;
	for (int i = 1; i < n+1; ++i)
	{
		for (int j = 1; j < n+1; ++j)
		{
			dis[i][j] = INF;
		}
	}
	for (int i = 0; i < m; ++i)
	{
		int u, v, w;
		cin >> u >> v >> w;
		dis[u][v] = dis[v][u] = w;
	}
	int k;
	cin >> k;
	int minPathLen = INF;
	int minPathNum = 0;
	for (int i = 0; i < k; ++i)
	{
		int num;
		cin >> num;
		memset(vis, 0, sizeof(vis));
		int circle[num];
		int pathLen = 0;
		for (int j = 0; j < num; ++j)
		{
			int t;
		    cin >> t;
			vis[t] = 1;
			circle[j] = t;
		}
		for (int j = 1; j < num; ++j)
		{
			int node1 = circle[j-1], node2 = circle[j];
			pathLen += dis[node1][node2];
		}
        bool flag = true;
        for (int j = 1; j < n+1; ++j)
        {
        	if(vis[j]==0) flag=false;
        }
		if(circle[0]!=circle[num-1] || !flag || pathLen>=INF)
		{
			cout << "Path " << i+1 << ": ";
			if(pathLen>=INF) cout << "NA ";
			else cout << pathLen << " ";
			cout << "(Not a TS cycle)" << endl;
		}
		else if(flag && num!=n+1 && pathLen<=INF)
		{
			if(pathLen<minPathLen)
			{
				minPathLen = pathLen;
				minPathNum = i+1;
			}
			cout << "Path " << i+1 << ": " << pathLen << " " << "(TS cycle)" << endl;
		}
		else if(flag && num==n+1 && pathLen<=INF)
		{
			if(pathLen<minPathLen)
			{
				minPathLen = pathLen;
				minPathNum = i+1;
			}
			cout << "Path " << i+1 << ": " << pathLen << " " << "(TS simple cycle)" << endl;
		}
	}
	cout << "Shortest Dist(" << minPathNum << ") = " << minPathLen << endl;
	return 0;
}
上一篇:Codeforces 1150


下一篇:hdu 1150