Pagini recente » Cod sursa (job #2641591) | Istoria paginii runda/baraj_lasm_cl_xi_xii/clasament | Cod sursa (job #2713046) | Cod sursa (job #2713040) | Cod sursa (job #2703380)
#include <bits/stdc++.h>
using namespace std;
ifstream f("adn.in");
ofstream g("adn.out");
struct wow
{
int poz;
int fr[20];
vector <int> v;
int cost;
}b,acum;
queue <wow> q;
vector <int> sol,v1;
int n,i,j,urm[30005],k,cost[20][20],fr[20],ok,maxim,ok1[20];
string s[20],s2;
int main()
{
f>>n;
for (i=1;i<=n;i++)
{
f>>s[i];
}
for (i=1;i<=n;i++)
{
for (j=1;j<=n;j++)
{
if (i!=j)
{
s2=s[j]+'#'+s[i];
urm[0]=0;
k=0;
for (int t=1;t<s2.size();t++)
{
while (k>0&&s2[t]!=s2[k])
{
k=urm[k-1];
}
if (s2[t]==s2[k])
{
k++;
}
urm[t]=k;
if (urm[t]==s[j].size())
{
ok1[j]=1;
}
}
cost[i][j]=urm[s2.size()-1];
}
}
}
int minim=1e9;
for (i=1;i<=n;i++)
{
for (j=1;j<=n;j++)
{
b.fr[j]=ok1[j];
}
b.v.clear();
b.v.push_back(i);
b.cost=s[i].size();
b.poz=i;
b.fr[i]=1;
q.push(b);
while (!q.empty())
{
acum=q.front();
q.pop();
ok=0;
for (j=1;j<=n;j++)
{
if (acum.fr[j]==0)
{
ok=1;
break;
}
}
if (ok==0)
{
if (acum.cost<minim)
{
minim=acum.cost;
sol.clear();
for (j=0;j<acum.v.size();j++)
{
sol.push_back(acum.v[j]);
}
}
}
else
{
for (j=1;j<=n;j++)
{
b=acum;
if (acum.fr[j]==0)
{
b.v.push_back(j);
b.fr[j]=1;
b.cost=b.cost+s[j].size()-cost[acum.v[acum.v.size()-1]][j];
b.poz=j;
q.push(b);
}
}
}
}
}
g<<s[sol[0]];
for (i=1;i<sol.size();i++)
{
int val1=sol[i-1],val2=sol[i];
for (j=cost[val1][val2];j<s[val2].size();j++)
{
g<<s[val2][j];
}
}
return 0;
}