Cod sursa(job #2418735)

Utilizator Laura_CorneiLaura Maria Cornei Laura_Cornei Data 6 mai 2019 07:55:02
Problema Ciclu hamiltonian de cost minim Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.15 kb
#include <fstream>
#include <vector>
#define inf 324000000
using namespace std;
fstream f1("hamilton.in", ios::in);
fstream f2("hamilton.out", ios::out);
int n, m, dp[262155][20], ct[20][20]; ///dp[j][k]=ctmin ciclu ham. care incepe din 1 se termina in k si contine nodurile din config j
vector<int> v[20];
int main(){

    int i, j, k, x, y, c, ans;
    f1>>n>>m;
    for(i=0; i<n; i++)
        for(j=0; j<n; j++)
             ct[i][j]=inf;

    for(i=1; i<=m; i++){
        f1>>x>>y>>c;
        ct[x][y]=c;
        v[y].push_back(x);
    }
    for(i=0; i<(1<<n); i++)
        for(j=0; j<n; j++)
             dp[i][j]=inf;

    dp[1][0]=0;

    for(j=0; j<(1<<n); j++)
        for(k=0; k<n; k++)
            if(j&(1<<k))
        for(auto it=v[k].begin(); it!=v[k].end(); ++it)
            if((ct[*it][k]!=inf)&&(j&(1<<(*it)))){
            i=*it;
            dp[j][k]=min(dp[j][k], dp[j^(1<<k)][i]+ct[i][k]);
        }
    ans=inf;
    for(auto it=v[0].begin(); it!=v[0].end(); ++it)
       if(ct[*it][0]!=inf) ans=min(ans, dp[(1<<n)-1][*it]+ ct[*it][0]);
    if(ans>=inf ) f2<<"Nu exista solutie";
    else f2<<ans;
    return 0;
}