Pagini recente » Cod sursa (job #300877) | Cod sursa (job #2665234) | Cod sursa (job #249037) | Cod sursa (job #2963829) | Cod sursa (job #1209402)
#include <cstdio>
#include <vector>
#include <queue>
#define Nmax 20
#define INF 2000000000
using namespace std;
struct Edge
{
int nod,cost;
};
struct el
{
int nod,stare;
};
vector <Edge> L[Nmax];
queue <el> Q;
int dp[(1<<20)],N;
inline void Dinamic()
{
el w,w1;
vector <Edge>:: iterator it;
w.nod=1; w.stare=0; Q.push(w);
while(!Q.empty())
{
w=Q.front(); Q.pop();
for(it=L[w.nod].begin();it!=L[w.nod].end();++it)
if(!((1<<(it->nod-1))&w.stare))
if(dp[w.stare+(1<<(it->nod-1))]>dp[w.stare]+it->cost)
{
dp[w.stare+(1<<(it->nod-1))]=dp[w.stare]+it->cost;
w1.nod=it->nod; w1.stare=w.stare+(1<<(it->nod-1));
Q.push(w1);
}
}
}
int main()
{
int M,a,b,c,i;
Edge w;
freopen ("hamilton.in","r",stdin);
freopen ("hamilton.out","w",stdout);
scanf("%d%d", &N,&M);
while(M--)
{
scanf("%d%d%d", &a,&b,&c);
++a; ++b;
w.nod=b; w.cost=c;
L[a].push_back(w);
}
for(i=1;i<(1<<N);++i)
dp[i]=INF;
Dinamic();
if(dp[(1<<N)-1]!=INF)
printf("%d\n", dp[(1<<N)-1]);
else
printf("Nu exista solutie\n");
return 0;
}