Cod sursa(job #2476895)

Utilizator DavidLDavid Lauran DavidL Data 19 octombrie 2019 12:14:06
Problema Ubuntzei Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.13 kb
#include <bits/stdc++.h>
#define cin fi
#define cout fo
using namespace std;
ifstream fi("ubuntzei.in");
ofstream fo("ubuntzei.out");

const int KMAX = 18;
const int NMAX = 2005;
const int INF = 1e9;

int n, m, k;
int p[KMAX];
bool special[NMAX];
int dist[KMAX][NMAX];
vector < pair<int, int> > G[NMAX];
int dp[KMAX][(1 << KMAX)];

void dijkstra(int ind)
{
    for (int i = 1; i <= n; i++)
        dist[ind][i] = INF;

    priority_queue < pair<int, int> > Q;

    dist[ind][p[ind]] = 0;
    Q.push({0, p[ind]});

    while (!Q.empty())
    {
        int nod = Q.top().second, distAici = -Q.top().first;
        Q.pop();

        if (dist[ind][nod] != distAici)
            continue;

        for (auto v: G[nod])
        {
            int distNou = dist[ind][nod] + v.second;
            if (distNou < dist[ind][v.first])
            {
                dist[ind][v.first] = distNou;
                Q.push({-dist[ind][v.first], v.first});
            }
        }
    }
}

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

    dp[0][1] = 0;

    for (int mask = 2; mask < (1 << (k + 1)); mask++)
    {
        for (int i = 0; i <= k; i++)
            if (mask & (1 << i))
            {    
                int maskFara = (mask ^ (1 << i));
                dp[i][mask] = INF;

                for (int j = 0; j <= k; j++)
                    dp[i][mask] = min(dp[i][mask], dp[j][maskFara] + dist[i][p[j]]);
            }
    }
}

int main()
{
    cin >> n >> m;
    cin >> k;
    for (int i = 1; i <= k; i++)
    {
        cin >> p[i];
        special[p[i]] = 1;
    }

    for (int i = 1; i <= m; i++)
    {
        int u, v, c;
        cin >> u >> v >> c;
        G[u].push_back({v, c});
        G[v].push_back({u, c});
    }

    p[0] = 1;
    p[k + 1] = n;

    for (int i = 0; i <= k + 1; i++)
    {
        dijkstra(i);
    }

    getDp();

    int rez = INF;
    for (int i = 0; i <= k; i++)
            rez = min(rez, dp[i][(1 << (k + 1)) - 1] + dist[i][n]);

    cout << rez;

    return 0;
}