添加链接描述
图的遍历连通性用邻接矩阵
#includeusing namespace std;const int N=210;int mp[N][N];int main(){ int n,m; cin>>n>>m; for(int i=1;i<=m;i++){ int a,b,c; cin>>a>>b>>c; mp[a][b]=c; mp[b][a]=c; } int q; cin>>q; int res_id=0,res_dist=0x3f3f3f3f; for(int p=1;p<=q;p++){ int k,ok_connect=1,dist=0; sets; cin>>k; vectorarr(k); for(int i=0;i>arr[i]; s.insert(arr[i]); if(i){ if(mp[arr[i]][arr[i-1]]==0){ok_connect=0; // cout< } else { dist+=mp[arr[i]][arr[i-1]]; } } } printf("Path %d: ",p); if(ok_connect)cout<dist){ res_dist=dist; res_id=p; } } else if(s.size()==n&&arr[0]==arr[k-1]&&ok_connect){ cout<<" (TS cycle)"<dist){ res_dist=dist; res_id=p; } } else { cout<<" (Not a TS cycle)"<