比赛 20120330 评测结果 AAAAAAAAAA
题目名称 字符串子串 最终得分 100
用户昵称 Makazeu 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2012-03-30 21:51:26
显示代码纯文本
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <queue>
using namespace std;
const int MAXN=10;
int top=0;
int N;
int cmp(const void *a, const void *b)  
{   
    return strcmp((*(string*)a).data(),(*(string*)b).data());
}   
string s[MAXN];
string ans[50000];

class QUEUE
{
public:
	int flag[9];
	string st;
	int num;
	void clr()
	{
		num=0;
		for(int i=1;i<=N;i++) flag[i]=0;
		st.clear();
	}	
};

queue <QUEUE> Q;
void bfs()
{
	QUEUE tmp,nxt;
	tmp.clr();
	Q.push(tmp);
	while(!Q.empty())
	{
		tmp=Q.front();
		Q.pop();
		if(tmp.num==N)
		{
			top++;
			ans[top]=tmp.st;
			continue;
		}
		for(int i=1;i<=N;i++)
		{
			if(tmp.flag[i]) continue;
			nxt=tmp;
			nxt.flag[i]=1;
			for(unsigned int k=0;k<s[i].length();k++)
				nxt.st.push_back(s[i][k]);
			nxt.num++;
			Q.push(nxt);
		}
	}
}

int main()
{
	freopen("substring.in","r",stdin);
	freopen("substring.out","w",stdout);
	scanf("%d\n",&N);
	char str[200];
	string temp;
	for(int k=1;k<=N;k++)
	{
		temp.clear();
		memset(str,'\0',sizeof(str));
		scanf("%s\n",&str);
		for(unsigned int i=0;i<strlen(str);i++) temp.push_back(str[i]);
		s[k]=temp; 
	}
	bfs();
	qsort(ans+1,top,sizeof(ans[0]),cmp);
	printf("%s",ans[1].data());
	return 0;
}