Submission #462493

---

Source Code Expand

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;


int Max = 0;
string goal_way;
class Pass
{
public:
	bool way[8][8];
	void Set()
	{
		for(int i = 0; i < 8; i++)
			for(int j = 0; j <8; j++)
				way[i][j] = false;
	
	}
};
int N;
vector<string> name_list;
bool way[8][8]= {0};
int GoalID1;
int GoalID2;
bool solve(int n, int nowID,bool reach,vector<int> way,Pass pass);

int main()
{
	cin >> N;
	string name;
	for(int i = 0; i < N; i++)
	{
		cin >> name;
		name_list.push_back(name);
	}
	sort(name_list.begin(),name_list.end());
	int m;
	cin >> m;
	string p1,p2;
	int ID1,ID2;
	Pass pass;
	pass.Set();
	for(int i = 0; i < m; i++)
	{
		cin >> p1 >> p2;
		for(int j = 0;j < N; j++)
		{
			if(name_list[j] == p1)
			{
				ID1 = j;
				break;
			}
		}
		for(int j = 0;j < N; j++)
		{
			if(name_list[j] == p2)
			{
				ID2 = j;
				break;
			}
		}
		pass.way[ID1][ID2] = true;
		pass.way[ID2][ID1] = true;
	}
	cin >> p1 >> p2;
	for(int j = 0;j < N; j++)
	{
		if(name_list[j] == p1)
		{
			GoalID2 = j;
			break;
		}
	}
	for(int j = 0;j < N; j++)
	{
		if(name_list[j] == p2)
		{
			GoalID1 = j;
			break;
		}
	}
	vector<int> way;
	solve(0,GoalID2,false,way,pass);

	cout << goal_way << endl;
}

bool solve(int n, int nowID,bool reach,vector<int> way,Pass pass)
{

	if( Max != 0)
		if(n > Max|| n > N*(N-1)/2)
			return false;
	if(nowID == GoalID2 && reach)
	{
	
		string answer;
		for(int i = 0; i < n; i++)
		{
			answer += name_list[way[i]];
		}

		if(Max == 0 || Max > n)
		{
			Max = n;
			goal_way = answer;
		}
		else if(Max == n)
		{
			if(strcmp(goal_way.c_str(),answer.c_str()) > 0 )
				goal_way = answer;
		}
		return true;
	}
	
	way.push_back(nowID);
	if(nowID == GoalID1)
		reach = true;
	for(int i = 0; i < N; i++)
	{
		if(pass.way[i][nowID] == true)
		{
			pass.way[i][nowID] = false;
			pass.way[nowID][i] = false;
			solve(n+1,i,reach,way,pass);
			pass.way[i][nowID] = true;
			pass.way[nowID][i] = true;
		}
	}

	
}

Submission Info

Judge Result