Problem 1108 : A Long Ride on a Railway

問題概要

無向グラフで表せる鉄道網与えられる。
このとき、ある駅から出発して、同じ線路を2度以上とおらないようなパスのうち、最も長さの長いパスを出力せよ。
同じ駅は何度通ってもよいものとする。

駅の数は10以下、線路の数は20以下である。

解法

線路の数、駅の数ともに少ないので、全探索で十分間に合う。

ソースコード

int n,m;
vector<vector<pi> >e;
bool use[11][11];
int mxl; vi ans,tmp;

void dfs(int c,int s)
{
	bool f=1;
	tmp.pb(c);
	fr(i,e[c])
	{
		int h=c,t=i->first;
		if(h>t)swap(h,t);
		if(use[h][t])continue;
		use[h][t]=1;
		dfs(i->first,s+i->second);
		f=use[h][t]=0;
	}
	if(f)
	{
		if(mxl<s||mxl==s&&ans>tmp)
		mxl=s,ans=tmp;
	}
	tmp.pop_back();
}
int main()
{
	while(scanf("%d%d",&n,&m),n)
	{
		e.clear(); e.resize(n+1);
		ans.clear(); ans.pb(inf);
		rep(i,m)
		{
			int a,b,c; scanf("%d%d%d",&a,&b,&c);
			e[a].pb(mp(b,c)); e[b].pb(mp(a,c));
		}
		mxl=0;
		for(int i=1;i<=n;i++)
		{
			rep(j,11)rep(k,11)use[i][j]=0;
			tmp.clear(); dfs(i,0);
		}
		printf("%d\n",mxl);
		int na=ans.size();
		rep(i,na)printf("%d%c",ans[i],i==na-1?'\n':' ');
	}
	return 0;
}