1150 traveling salesman problem (25 points)

maxmin

1150 Travelling Salesman Problem (25 branch )

The question

Give an undirected graph , and k Paths , Determine which paths are simple loops , Not a simple loop , Non loop , Disconnected path . And find the least expensive way in the loop .
1. Simple loop ： Except for the starting point, all other points pass through once , And start from the starting point and finally return to the starting point .
2. Not a simple loop ： From the beginning , Finally back to the starting point , Each point passes at least once .
3. Non loop ： Not passing through all points or starting and ending points are different .（ It is not without rings ）
4. Unconnected ： The path is disconnected .

Ideas

Traverse every path , When there is an unconnected path, it is directly 4, A little bit has not passed or the starting point and ending point are different 3, be left over , There are only nodes in the path +1 The path of nodes of is 1, The last remaining is 2.
Find the minimum cost in the loop .
Note that the initialization is a little larger when finding the minimum cost （>1e5), The last test point card .

Code

#include<stdio.h>
#include<vector>
#include<string.h>
using namespace std;
int mp[507][507];
int main()
{
    
	int n,m,a,b,c,k,x,y[507],last,vis[507],sum,flog=0,xmin=100000,xxx;//xmin initial value >=1e5
	vector<int>s;
	memset(mp,0,sizeof(mp));
	scanf("%d%d",&n,&m);
	for(int i=0;i<m;i++){
    
		scanf("%d%d%d",&a,&b,&c);
		mp[a][b]=c;
		mp[b][a]=c;
	}
	scanf("%d",&k);
	for(int i=0;i<k;i++){
    
		scanf("%d",&x);
		flog=0;
		sum=0;
		memset(vis,0,sizeof(vis));
		for(int j=0;j<x;j++){
    
			scanf("%d",&y[j]);
			if(j!=0){
    
// printf("#\n");
				if(flog!=1&&mp[last][y[j]]!=0){
    
					sum+=mp[last][y[j]];
					vis[y[j]]=1;
					last=y[j];
				}else{
    
					flog=1;
				}
			}else{
    
				last=y[j];
				vis[y[j]]=1;
			}
		}
		if(flog==1){
    
			printf("Path %d: NA (Not a TS cycle)\n",i+1);
		}else{
    
			for(int j=1;j<=n;j++){
    
				if(vis[j]!=1){
    
					flog=1;
					break;
				}
			}
			if(flog==1||y[0]!=y[x-1]){
    
				printf("Path %d: %d (Not a TS cycle)\n",i+1,sum);
			}else if(x==n+1){
    
				printf("Path %d: %d (TS simple cycle)\n",i+1,sum);
				if(xmin>sum){
    
					xmin=sum;
					xxx=i+1;
				}
			}else{
    
				printf("Path %d: %d (TS cycle)\n",i+1,sum);
				if(xmin>sum){
    
					xmin=sum;
					xxx=i+1;
				}
			}
		}
	}
	printf("Shortest Dist(%d) = %d\n",xxx,xmin);
	return 0;
}