学步园

#include <cstdio>
#include <cstdlib>
#include <string>
#include <algorithm>
#include <vector>
#include <list>

using namespace std;

const int N = 10001;
const int INF = 2000000001;

class Edge
{
public: 
	int name;
	int to;
	int value;
	Edge(int name1 = 0, int to1 = 0, int val1 = 0):name(name1), to(to1), value(val1){}
};

// adj List of Graph
list<Edge> v[N];

bool vis[N];

// cur is the array of current edges, sumCur is the sum of cur array
// best is the currently the best solution
int best[N];
int sumBest = INF;
int cur[N];
int sumCur = 0;

// start vertex
int start;
// number of vertexs
int n;

int getStart()
{
	for(int i = 0; i < N; i++)
	{
		if(!v[i].empty())
		{
			return i;
		}
	}
}

void dfs(int s, int length)
{
	//printf("enter visiting %d\n", s);

	list<Edge> es = v[s];
	list<Edge>::iterator it;

	for(it = es.begin(); it != es.end(); it++)	
	{
		int t = it->to;
		if(t == start && length == n)
		{
			// printf("find a solution\n");
			// find a solution
			if(sumCur + it->value < sumBest)
			{
				sumBest = sumCur + it->value;
				cur[length] = it->name;
				copy(cur, cur+N, best);
			}
			return;
		}
		else
		{
			if(!vis[t])
			{
				//printf("=> %d\n", t);
				vis[t] = true;	
				sumCur += it->value;
				cur[length] = it->name;
				dfs(t, length+1);
				sumCur -= it->value;
				vis[t] = false;
				//printf("<= %d\n", t);
			}
		}
	}	

	//printf("exit visiting %d\n", s);
}

void solve()
{
	start = getStart();

	vis[start] = true;
	dfs(start, 1);

	printf("%d\n", sumBest);

	sort(best+start, best+n+1);
	for(int i = start; i <= n; i++)
	{
		printf("%d ", best[i]);
	}
	printf("\n");
}

void init()
{
	char m[10];
	char s[10];
	char t[10];
	int val;

	while(scanf("%s%s%s%d", m, s, t, &val) != EOF)
	{
		//printf("%s %s %s %d\n", m, s, t, val);

		string sm(m); 
		string ss(s); 
		string st(t);

		int im, is, it;
		im = atoi(sm.substr(1).c_str());
		is = atoi(ss.substr(1).c_str());
		it = atoi(st.substr(1).c_str());

		Edge e(im, it, val);
		v[is].push_front(e);
	}

	for(int i = 0; i < N; i++)
	{
		if(!v[i].empty())
		{
			n++;
		}
	}

	/* print the graph
	for(int i = 0; i < N; i++)
	{
		if(!v[i].empty())
		{
			list<Edge> es = v[i];

			list<Edge>::iterator it;

			for(it = es.begin(); it != es.end(); it++)
			{
				printf("%d %d %d\n", i, it->to, it->value);
			}
		}
	}  */
}

int main()
{
	init();
	solve();
	return 0;
}

see: http://www.mitibar.com/superdrink.php, code is implemented according to hamilton loop, not suitable to all cases.