# Cod sursa(job #2764934)

Utilizator Data 23 iulie 2021 17:13:12 Ubuntzei 100 cpp-64 done Arhiva de probleme 1.76 kb
``````#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define KMAX 17
#define PI pair <int, int>
#define NMAX 2005

using namespace std;

ifstream f("ubuntzei.in");
ofstream g("ubuntzei.out");

int n, m, k, a[NMAX], drum[NMAX], d[NMAX][NMAX];
int dp[1 << KMAX][KMAX];
vector <PI> Muchii[NMAX];
priority_queue <PI, vector <PI>, greater<PI>> q;

void dijkstra(int nod)
{
for(int i = 1; i <= n; i++)
drum[i] = INF;
q.push({0, nod});
drum[nod] = 0;
while(!q.empty())
{
PI nod = q.top();
q.pop();
for(auto child : Muchii[nod.second])
if(drum[child.first] > drum[nod.second] + child.second)
{
drum[child.first] = drum[nod.second] + child.second;
q.push({drum[child.first], child.first});
}
}
}

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

for(int i = 1; i <= k; i++)
f >> a[i];
a[0] = 1;
a[k + 1] = n;

for(int i = 1; i <= m; i++)
{
int x, y, cost;
f >> x >> y >> cost;
Muchii[x].push_back({y, cost});
Muchii[y].push_back({x, cost});
}

for(int i = 0; i <= k + 1; i++)
{
dijkstra(a[i]);
for(int j = 0; j <= k + 1; j++)
d[i][j] = d[j][i] = drum[a[j]];
d[i][i] = INF;
}

for(int i = 0; i < (1 << (k + 2)); i++)
for(int j = 0; j <= k + 1; j++)
dp[i][j] = INF;

dp[0][0] = d[0][0] = 0;
for(int i = 0; i < (1 << (k + 2)); i++)
for(int j = 0; j <= k + 1; j++)
if(i & (1 << j))
for(int l = 0; l <= k + 1; l++)
dp[i][j] = min(dp[i][j], dp[i ^ (1 << j)][l] + d[j][l]);

g << dp[(1 << (k + 2)) - 1][k + 1];

return 0;
}
``````