Pagini recente » Rezultatele filtrării | Cod sursa (job #2440136) | Cod sursa (job #1974770) | Rezultatele filtrării | Cod sursa (job #650783)
Cod sursa(job #650783)
#include "stdio.h"
#define NMAX 20
#define INFINIT (1<<30)
int m_cost[NMAX][NMAX], m_sol[1<<NMAX][NMAX];
int min(int a,int b)
{
if(a<b)
return a;
return b;
}
int main()
{
int cost_min=INFINIT,noduri,muchii,i,j,aux;
FILE *in,*out;
in = fopen("hamilton.in", "r");
out = fopen("hamilton.out", "w");
fscanf(in,"%d %d", &noduri, &muchii);
for (i = 0; i < noduri; i++)
for (j = 0; j < noduri; j++)
m_cost[i][j] = INFINIT;
for (i = 0; i < (1 << noduri); i++)
for (j = 0; j < noduri; j++)
m_sol[i][j] = INFINIT;
while (muchii--)
{
int x, y, cost;
fscanf(in,"%d %d %d", &x, &y, &cost);
m_cost[x][y] = cost;
}
m_sol[1][0] = 0;
for (i = 0; i < (1 << noduri); i++)
for (j = 0; j < noduri; j++)
{
if (!(i & (1 << j)))
continue;
for (aux = 0; aux < noduri; aux++)
{
if (!(i & (1 << aux)) || (m_cost[aux][j] == INFINIT) || (aux == j) )
continue;
m_sol[i][j] = min(m_sol[i][j], m_sol[i - (1 << j)][aux] + m_cost[aux][j]);
}
}
for (i = 0; i < noduri; i++)
if (m_sol[(1 << noduri) - 1][i] != INFINIT)
cost_min = min(cost_min, m_sol[(1 << noduri) - 1][i] + m_cost[i][0]);
if (cost_min == INFINIT)
fprintf (out,"Nu exista solutie");
else
fprintf (out,"%d", cost_min);
fclose(in);
fclose(out);
return 0;
}