【1150】Travelling Salesman Problem (25分)【图论】

  

   

    

     

    
    

     

      #include<iostream>
     
    
   

    

     

    
    

     

      #include<stdio.h>
     
    
   

    

     

    
    

     

      #include<stdlib.h>
     
    
   

    

     

    
    

     

      #include<math.h>
     
    
   

    

     

    
    

     

      #include<string.h>
     
    
   

    

     

    
    

     

      #include<algorithm> 
     
    
   

    

     

    
    

     

      #include<map>
     
    
   

    

     

    
    

     

      #include<vector>
     
    
   

    

     

    
    

     

      #include<queue> 
     
    
   

    

     

    
    

     

      #include<string>
     
    
   

    

     

    
    

     

      #include<set>
     
    
   

    

     

    
    

     

      using namespace std;  
     
    
   

    

     

    
    

     

      //注意输出最后一句的空格格式
     
    
   

    

     

    
    

     

      int e[300][300],n,m,k,ans=99999999,ansid;
     
    
   

    

     

    
    

     

      vector<int>v;
     
    
   

    

     

    
    

     

      void check(int index){
     
    
   

    

     

    
    

     
	int sum=0,cnt,flag=1;
     
    
   

    

     

    
    

     
	scanf("%d",&cnt);//这条路径走的城市数cnt
     
    
   

    

     

    
    

     

      	set<int>s;
     
    
   

    

     

    
    

     

      	vector<int>v(cnt);
     
    
   

    

     

    
    

     
	for(int i=0;i<cnt;i++){
     
    
   

    

     

    
    

     
		scanf("%d",&v[i]);//存入查询的一条路径
     
    
   

    

     

    
    

     

      		s.insert(v[i]);
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	for(int i=0;i<cnt-1;i++){
     
    
   

    

     

    
    

     
		if(e[v[i]][v[i+1]]==0)  flag=0;
     
    
   

    

     

    
    

     
		//有相邻两点不可达则标记
     
    
   

    

     

    
    

     

      		sum+=e[v[i]][v[i+1]];
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	if(flag==0)
     
    
   

    

     

    
    

     
		printf("Path %d: NA (Not a TS cycle)\n",index);
     
    
   

    

     

    
    

     
	else if(v[0]!=v[cnt-1]||s.size()!=n)//点不够或首尾点不同
     
    
   

    

     

    
    

     
		printf("Path %d: %d (Not a TS cycle)\n",index,sum);
     
    
   

    

     

    
    

     
	else if(cnt!=n+1){//注意回到原点(初末点记2次)
     
    
   

    

     

    
    

     
		printf("Path %d: %d (TS cycle)\n",index,sum);
     
    
   

    

     

    
    

     
		if(sum<ans){
     
    
   

    

     

    
    

     

      			ans=sum;//更新成功解min
     
    
   

    

     

    
    

     

      			ansid=index;
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     

      	}else{//剩下是最难搞的“简单圆”
     
    
   

    

     

    
    

     
		printf("Path %d: %d (TS simple cycle)\n",index,sum);
     
    
   

    

     

    
    

     
		if(sum<ans){
     
    
   

    

     

    
    

     

      			ans=sum;//更新成功解min
     
    
   

    

     

    
    

     

      			ansid=index;
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      int main(){
     
    
   

    

     

    
    

     
	scanf("%d%d",&n,&m);//n个城市，m条边
     
    
   

    

     

    
    

     
	for(int i=0;i<m;i++){
     
    
   

    

     

    
    

     
		int t1,t2,t;
     
    
   

    

     

    
    

     
		scanf("%d%d%d",&t1,&t2,&t);//t1到t2距离为t
     
    
   

    

     

    
    

     

      		e[t1][t2]=e[t2][t1]=t;
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	scanf("%d",&k);//查询k次
     
    
   

    

     

    
    

     
	for(int i=1;i<=k;i++)  check(i);
     
    
   

    

     

    
    

     
	printf("Shortest Dist(%d) = %d\n",ansid,ans);
     
    
   

    

     

    
    

     
	system("pause");
     
    
   

    

     

    
    

     
	return 0;
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: andyguo.blog.csdn.net，作者：山顶夕景，版权归原作者所有，如需转载，请联系作者。

原文链接：andyguo.blog.csdn.net/article/details/104034828