Cod sursa(job #3376484)

Utilizator JenJenCristache Ion JenJen Data 17 noiembrie 2026 22:14:13
Problema Ciclu hamiltonian de cost minim Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.3 kb
#include <fstream>
using namespace std;

ifstream cin ("hamilton.in");
ofstream cout ("hamilton.out");

int n, m;
int x, y, c;
int cost[20][20];
int dp[20][1 << 18];
int minn = 1e9;
int main()
{
    cin >> n >> m;

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cost[i][j] = 1e9;
        }
    }

    for (int i = 1; i <= m; i++)
    {
        cin >> x >> y >> c;
        cost[x][y] = c;
    }

    for (int mask = 0; mask < (1 << n); mask++)
    {
        for (int nod = 0; nod < n; nod++)
        {
           dp[nod][mask] = 1e9;
        }
    }

    dp[0][1] = 0;

    for (int mask = 0; mask < (1 << n); mask++)
    {
        for (int nod = 0; nod < n; nod++)
        {
            if (mask >> nod & 1)
            {
                for (int bit = 0; bit < n; bit++)
                {
                    if (mask >> bit & 1 && bit != nod)
                    {
                        dp[nod][mask] = min(dp[nod][mask], dp[bit][mask - (1 << nod)] + cost[bit][nod]);
                    }
                }
            }
        }
    }


    for (int i = 1; i < n; i++)
    {
        if (cost[i][0] != 1e9)
        minn = min(minn, dp[i][(1 << (n)) - 1] + cost[i][0]);
    }


    cout << minn;
    return 0;
}