Cod sursa(job #3375840)

Utilizator Vcitor09Solcanu Victor Vcitor09 Data 14 noiembrie 2026 09:50:54
Problema Ciclu hamiltonian de cost minim Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.11 kb
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
int n,m,p,dp[1<<18][20],x,y,z;
vector<pair<int,int>>v[20];
vector<pair<int,int>>inv[20];
int main()
{
    freopen("hamilton.in","r",stdin);
    freopen("hamilton.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;++i){
        cin>>x>>y>>z;
        x++;
        y++;
        v[x].push_back({z,y});
        inv[y].push_back({z,x});
    }
    for(int i=0;i<(1<<n);++i){
        for(int j=0;j<=n;++j) dp[i][j]=1e9+5;
    }
    dp[1][1]=0;
    for(int mask=0;mask<(1<<n);++mask){
        for(int i=1;i<=n;++i){
            if((1<<(i-1)) & mask){
                for(auto [cost,nod] : v[i]){
                    if(!((1<<(nod-1)) & mask))
                        dp[mask][nod]=min(dp[mask-(1<<(i-1))][i]+cost,dp[mask][nod]);
                }
            }
        }
    }
    int mini=1e9+5;
    for(auto [cost,nod] : inv[1]){
        mini=min(mini,dp[(1<<n)-1][nod] + cost);
    }
    if(mini==1e9+5) cout<<"Nu exista solutie";
    else cout<<mini;
    return 0;
}