Submission #168759

#	Time	Username	Problem	Language	Result	Execution time	Memory
168759		combi1k1	Cities (BOI16_cities)	C++14	100 / 100	2415 ms	46824 KiB

cities

#pragma GCC optimize "-O3"
#include<bits/stdc++.h>

using namespace std;

#define ll  long long
#define X   first
#define Y   second

#define pb  emplace_back

const int   N   = 1e5 + 1;
const ll    inf = 1e18;

typedef pair<ll,int>    ii;

vector<ii>  g[N];
vector<ll>  f[32];

int main()  {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n;  cin >> n;
    int k;  cin >> k;
    int m;  cin >> m;

    vector<int> imp(k);

    for(int&x : imp)
        cin >> x,
        x--;

    for(int i = 0 ; i < m ; ++i)    {
        int x;  cin >> x;   --x;
        int y;  cin >> y;   --y;
        int c;  cin >> c;

        g[x].pb(c,y);
        g[y].pb(c,x);
    }
    for(int i = 0 ; i < 32 ; ++i)
        f[i].assign(n,inf);

    for(int i = 0 ; i < k ; ++i)
        f[1 << i][imp[i]] = 0;

    priority_queue<ii,vector<ii>,greater<ii> >  pq;

    for(int c = 1 ; c < (1 << k) ; ++c) {
        for(int a = c ; a ; a = (a - 1) & c)
        for(int i = 0 ; i < n ; ++i)
            if (f[c][i] > f[a][i] + f[c ^ a][i])
                f[c][i] = f[a][i] + f[c ^ a][i];

        for(int i = 0 ; i < n ; ++i)    if (f[c][i] != inf)
            pq.push(ii(f[c][i],i));

        while (pq.size())   {
            ll du = pq.top().X;
            int u = pq.top().Y;

            pq.pop();

            if (du != f[c][u])
                continue;

            for(ii  e : g[u])   {
                int v = e.Y;
                ll  C = e.X;

                if (f[c][v] > du + C)   {
                    f[c][v] = du + C;
                    pq.push(ii(f[c][v],v));
                }
            }
        }
    }

    ll  ans = inf;

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

    cout << ans << endl;
}

• Subtask 1: 22 / 22
• Subtask 2: 14 / 14
• Subtask 3: 15 / 15
• Subtask 4: 23 / 23
• Subtask 5: 26 / 26