Cod sursa(job #2594805)

Utilizator betybety bety bety Data 6 aprilie 2020 17:18:18
Problema ADN Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.7 kb
#include <cstdio>

#include <string>

#include <iostream>

#include <vector>

#include <cstring>

using namespace std;

const int NMAX = 18;

const int INF = 2.e9;

struct muchii

{

    int nod , cost , poz;

};

muchii temp;

vector <muchii> G[NMAX + 5];

vector <string> v;

vector <int> ans;

string s;

int d[1 << 18][NMAX + 1] , pr[1 << 18][NMAX + 1] , fbd;

int verif(int x , int y , int i)

{

    int j , n;

    n = min(v[x].length() , i + v[y].length());

    for(j = 0 ; i < n ; i ++ , j ++)

        if(v[x][i] != v[y][j])

            return 0;

    return 1;

}

int cauta(int x , int y)

{

    int i;

    for(i = 0 ; i < v[x].size() ; i ++)

        if(verif(x , y , i) == 1)

            return i;

    return -1;

}

int unionstr(int x , int y)

{

    int poz = cauta(x , y);

    if(poz == -1)

    {

        temp.nod = y;

        temp.cost = v[y].size();

        temp.poz = 0;

        G[x].push_back(temp);

    }

    else if(poz + v[y].length() > v[x].length() && poz != 0)

    {

        temp.nod = y;

        temp.cost = poz + v[y].length() - v[x].length();

        temp.poz = v[x].length() - poz;

        G[x].push_back(temp);

    }

    else

    {

        if(poz == 0 && v[x].length() > v[y].length())

            fbd = (fbd | (1 << y));

        else if(poz == 0 && v[x].length() < v[y].length())

            fbd = (fbd | (1 << x));

        else if(poz == 0 && v[x].length() == v[y].length() && x < y)

            fbd = (fbd | (1 << x));

        else

            fbd = (fbd | (1 << y));

    }

}

void afisare(int x , int y)

{

    int i , j;

    for(i = 0 ; i < G[x].size() ; i ++)

        if(G[x][i].nod == y)

            break;

    for(j = G[x][i].poz ; j < v[y].length() ; j ++)

        printf("%c" , v[y][j]);

}

int main()

{

    freopen("adn.in" , "r" , stdin);

    freopen("adn.out" , "w" , stdout);

    int n , i , j , lim , k , bm , l , c , lmin , aux;

    scanf("%d\n" , &n);

    for(i = 1 ; i <= n ; i ++)

    {

        getline(cin , s);

        v.push_back(s);

    }

    for(i = 0 ; i < n ; i ++)

        for(j = 0 ; j < n ; j ++)

            if(i != j)

                unionstr(i , j);

    lim = (1 << n) - 1;

    for(i = 0 ; i <= lim ; i ++)

        for(j = 0 ; j < n ; j ++)

            d[i][j] = INF;

    for(j = 0 ; j < n ; j ++)

        if((fbd & (1 << j)) == 0)

        {

            d[(1 << j)][j] = v[j].length();

            pr[(1 << j)][j] = -1;

        }

    for(i = 0 ; i <= lim ; i ++)

        for(j = 0 ; j < n ; j ++)

            if((i & (1 << j)) != 0)

                for(k = 0 ; k < G[j].size() ; k ++)

                    if((fbd & (1 << G[j][k].nod)) == 0)

                    {

                        bm = (i | (1 << G[j][k].nod));

                        if(d[bm][G[j][k].nod] > d[i][j] + G[j][k].cost)

                        {

                            d[bm][G[j][k].nod] = d[i][j] + G[j][k].cost;

                            pr[bm][G[j][k].nod] = j;

                        }

                    }

    l = (lim ^ fbd);

    lmin = INF;

    for(j = 0 ; j < n ; j ++)

        if(d[l][j] < lmin)

        {

            lmin = d[l][j];

            c = j;

        }

    ans.push_back(c);

    while(pr[l][c] != -1)

    {

        ans.push_back(pr[l][c]);

        aux = pr[l][c];

        l = (l ^ (1 << c));

        c = aux;

    }

    printf("%s" , v[ans[ans.size() - 1]].c_str());

    for(i = ans.size() - 1 ; i > 0 ; i --)

        afisare(ans[i] , ans[i - 1]);

    return 0;

}