【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;
}