Cod sursa(job #2681307)

Utilizator petrisorvmyVamanu Petru Gabriel petrisorvmy Data 5 decembrie 2020 11:29:14
Problema Ubuntzei Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.49 kb
#include <bits/stdc++.h>
#define fast ios_base :: sync_with_stdio(0); cin.tie(0);
#pragma GCC optimize("O3")
#define FILE_NAME "ubuntzei"
#define NMAX 2000 + 100
#define vs nod<<1
#define vd nod<<1|1
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pi;
typedef pair<ll,ll> llp;
typedef pair<ld,ld> pct;

const int inf = 1 << 29;
const ll mod = 1e9 + 7;
const ld eps = 1e-9;

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

inline void add(ll &a , ll b)
{
    a += b;
    a %= mod;
}

inline void sub(ll &a, ll b)
{
    a = (a - b + mod) % mod;
}

int n, m, pd[1 << 17][20];
int oras[20],k,dist[17][NMAX],distS[NMAX];
vector <pi> G[NMAX];
void Dijkstra(int start, int dst[])
{
    for(int i = 1; i <= n; ++i)
        dst[i] = inf;
    dst[start] = 0;
    set <pi> Q;
    Q.insert({0,start});
    while(!Q.empty())
    {
        int nod = (*Q.begin()).second;
        Q.erase(Q.begin());
        for(auto nxt : G[nod])
            if(dst[nod] + nxt.second <= dst[nxt.first])
            {
                if(dst[nxt.first] != inf)
                    Q.erase(Q.find({dst[nxt.first], nxt.first}));
                dst[nxt.first] = dst[nod] + nxt.second;
                Q.insert({dst[nxt.first], nxt.first});
            }
    }
}
int main()
{
    f >> n >> m >> k;
    for(int i = 1; i <= k; ++i)
        f >> oras[i];
    for(int i = 1; i <= m; ++i)
    {
        int x,y, z;
        f >> x >> y >> z;
        G[x].push_back({y,z});
        G[y].push_back({x,z});
    }
    Dijkstra(1, distS);

    if(k == 0)
        g << distS[n];
    else{

        for(int i = 1; i <= k; ++i)
            Dijkstra(oras[i], dist[i]);

        int W = 1 << k; W--;
        for(int i = 0; i <= W; ++i)
            for(int j = 0; j <= k; ++j)
                pd[i][j] = inf;

        for(int i = 1; i <= W; ++i)
            for(int j = 1; j <= k; ++j)
                if(i & (1 << (j - 1) ) != 0)
                {
                    int prev = i - (1 << (j - 1) );
                    if(prev == 0)
                        pd[i][j] = distS[oras[j] ];
                    else
                        for(int q = 1; q <= k; ++q)
                            pd[i][j] = min(pd[i][j], pd[prev][q] + dist[q][ oras[j] ]);
                }
        int sol = inf;
        for(int i = 1; i <=k; ++i)
            sol = min(sol, pd[W][i] + dist[i][n]);
        g << sol;
    }
    f.close();
    g.close();
    return 0;
}