# Cod sursa(job #2490022)

Utilizator Data 9 noiembrie 2019 16:28:13 Ubuntzei 100 cpp-64 done Arhiva de probleme 2.45 kb
``````#define MAX_NOD 2000
#define INF 0x3f3f3f3f

#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

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

struct Dublu
{
int nod, cost;

bool operator < (const Dublu& other) const { return cost > other.cost; }
};

int n, m, K, c[16];
vector<Dublu> G[MAX_NOD + 1];
vector<int> d, D[16];
vector<vector<int>> dp;

void Citire();
void Dijkstra(int nodStart, vector<int>& dist);

int main()
{
Citire();

Dijkstra(1, d);

if (K == 0)
{
fout << d[n];

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

int doiLaK = (1 << K);
dp = vector<vector<int>>(doiLaK + 1, vector<int>(K + 1, INF));

for (int i = 0; i < K; ++i)
{
Dijkstra(c[i], D[i]);
}

for (int j = 0; j < K; ++j)
{
dp[1 << j][j] = d[c[j]];
}

for (int i = 1; i < doiLaK; ++i)
{
for (int j = 0; j < K; ++j)
{
if (((i >> j) & 1) == 1)
{
for (int k = 0; k < K; ++k)
{
if (((i >> k) & 1) == 0)
{
dp[i | (1 << k)][k] = min(dp[i | (1 << k)][k], dp[i][j] + D[j][c[k]]);
}
}
}
}
}

int rasp = INF;
for (int i = 0; i < K; ++i)
{
rasp = min(rasp, dp[doiLaK - 1][i] + D[i][n]);
}

fout << rasp;

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

void Citire()
{
fin >> n >> m >> K;

for (int i = 0; i < K; ++i)
{ fin >> c[i]; }

int x, y, z;
for (int i = 0; i < m; ++i)
{
fin >> x >> y >> z;

G[x].push_back({ y, z });
G[y].push_back({ x, z });
}
}

void Dijkstra(int nodStart, vector<int>& dist)
{
dist = vector<int>(MAX_NOD + 1, INF);
dist[nodStart] = 0;

priority_queue<Dublu> Q;
Q.push({ nodStart, 0 });

while (!Q.empty())
{
Dublu nodFront = Q.top();
Q.pop();

if (dist[nodFront.nod] < nodFront.cost) { continue; }

for (const Dublu& vecin : G[nodFront.nod])
{
if (dist[vecin.nod] > (dist[nodFront.nod] + vecin.cost))
{
dist[vecin.nod] = dist[nodFront.nod] + vecin.cost;
Q.push({ vecin.nod, dist[vecin.nod] });
}
}
}
}
``````