题目描述
blablabla
样例
#include<bits/stdc++.h>
using namespace std;
const int N =210;
int n,m,k;
int v[N];
int g[N][N];
int cycle(int cnt)
{
int dist=0;
for(int i=0;i<cnt-1;i++)
{
if(g[v[i]][v[i+1]]==0) return 0;
else dist+=g[v[i]][v[i+1]];
}
return dist;
}
int main()
{
//freopen("1.txt","r",stdin);
cin>>n>>m;
for(int i=0;i<m;i++)
{
int a,b,c;cin>>a>>b>>c;
g[a][b]=g[b][a]=c;
}
cin>>k;
int min_dist=0x3f3f3f3f,id=0;
for(int i=1;i<=k;i++)
{
printf("Path %d: ",i);
int cnt;cin>>cnt;
set<int> st;
for(int j=0;j<cnt;j++)
{
cin>>v[j];st.insert(v[j]);
}
int dist=cycle(cnt);
if(dist)
{
printf("%d ",dist);
if(v[0]!=v[cnt-1])
{
puts("(Not a TS cycle)");continue;
}
if(st.size()==n)
{
if(dist<min_dist) min_dist=dist,id=i;
if(cnt-1==n) puts("(TS simple cycle)");
else puts("(TS cycle)");
}else puts("(Not a TS cycle)");
}
else puts("NA (Not a TS cycle)");
}
printf("Shortest Dist(%d) = %d", id, min_dist);
return 0;
}
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla