# Cod sursa(job #2519746)

Utilizator Data 8 ianuarie 2020 13:19:53 Gather 0 cpp-64 done Arhiva de probleme 2.84 kb
``````#include <bits/stdc++.h>

using namespace std;

ifstream fin("gather.in");
ofstream fout("gather.out");

const int oo = 2e9;
const int StareMax = 1 << 15;

int k, n, m;
int prizonieri[20];
int distanta[20][20][755];
int dp[20][ StareMax ], nrbits[ StareMax ];

struct Tunel
{
int x, lungime, capacitate;

bool operator <(const Tunel &e) const
{
return lungime < e.lungime;
}
};

vector <Tunel> L[1255];
priority_queue <Tunel> q;

void Init()
{
for(int i = 0; i <= k; i++)
for(int j = 0; j <= k; j++)
for(int w = 0; w <= n; w++)
distanta[i][j][w] = oo;

for(int j = 1; j < StareMax; j++)
for(int i = 1; i <= k; i++)
dp[i][j] = oo;
}

void Dijkstra(int nod, int nr)
{
distanta[nod][nr][prizonieri[nod]] = 0;
q.push({prizonieri[nod], 0, nr});

Tunel top;
while(!q.empty())
{
top = q.top();
q.pop();

for(auto i : L[top.x])
if(i.capacitate >= nr && distanta[nod][nr][i.x] > distanta[nod][nr][top.x] + i.lungime)
{
distanta[nod][nr][i.x] = distanta[nod][nr][top.x] + i.lungime;
q.push({i.x, distanta[nod][nr][i.x], nr});
}
}
}

int Nrbits(int a)
{
int cnt = 0;
while(a)
{
cnt++;
a >>= 1;
}
return cnt;
}

int main()
{
fin >> k >> n >> m;

for(int i = 1; i <= k; i++)
fin >> prizonieri[i];

int x, y, lg, c;
for(int i = 1; i <= m; i++)
{
fin >> x >> y >> lg >> c;

L[x].push_back({y, lg, c});
L[y].push_back({x, lg, c});
}

Init();

prizonieri[0] = 1;
Dijkstra(0, 0);
for(int id = 1; id <= k; id++)
for(int nr = 1; nr <= k; nr ++)
Dijkstra(id, nr);

for(int i = 1; i <= k; i++)
dp[i][ 1 << (i - 1) ] = distanta[0][0][prizonieri[i]];

int Smax = 1 << k;

for(int i = 1; i < Smax; i++)
nrbits[i] = Nrbits(i);

for(int stare = 1; stare < Smax; stare++)
for(int nod = 1; nod <= k; nod++)
if(stare & (1 << (nod - 1)))
for(int bit = 1; bit <= k; bit++)
if(!(stare & (1 << (bit - 1))))
{
dp[bit][stare + (1 << (bit - 1))] = min(
dp[nod][stare] + distanta[nod][nrbits[stare]][prizonieri[bit]],

dp[bit][stare + (1 << (bit - 1))]
);
}

int minim = oo;

for(int i = 1; i <= k; i++)
minim = min(minim, dp[i][Smax - 1]);

fout << minim << "\n";

fin.close();
fout.close();
return 0;
}
``````