Cod sursa(job #2568934)

Utilizator Anastasia11Susciuc Anastasia Anastasia11 Data 4 martie 2020 10:30:31
Problema Ciclu hamiltonian de cost minim Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.22 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
#define Nmax 100005
#define INF 0x3f3f3f3f

using namespace std;

ifstream f("hamilton.in");
ofstream g("hamilton.out");

int n, m;
int a[20][20];
vector <pair <int, int> > v[Nmax];
int dp[(1<<18)][18]; // am parcurs nodurile din reprez binara a lui i si suntem in j

int main()
{
    f >> n >> m;

    for (int i = 1, x, y, c; i <= m; i++)
    {
        f >> x >> y >> c;
        a[x][y]=c;
        v[x].push_back({y, c});
    }

    memset(dp, INF, sizeof(dp));
    int p=(1<<n);

    for (int i = 0; i < n; i++) dp[1][i]=0;

    for (int i = 1; i < p; i++)
    {
        for (int j = 0; j < n; j++)
            if (i&(1<<j))
            {
                for (auto k:v[j])
                {
                    int y=k.first, c=k.second;

                    if ((i&(1<<y)))
                    {
                        dp[i][j]=min(dp[i][j], dp[i-(1 << j)][y]+c);
                    }
                }
            }
    }

    int ans=INF;
    for (int i = 0; i < n; i++)
        if(a[0][i]!=0) ans=min(ans, dp[p-1][i]+a[0][i]);

    if (ans == INF) g << "Nu exista solutie";
    else g << ans;

    return 0;
}