Submission #674969

#	Time	Username	Problem	Language	Result	Execution time	Memory
674969		flashhh	Cities (BOI16_cities)	C++17	100 / 100	1951 ms	45000 KiB

cities

#include <bits/stdc++.h>
#define getbit(x,y) (((x)>>(y))&1)
#define getoff(x,y) ((x)^(1<<(y)))
#define bp __builtin_popcount

using namespace std;

int numVertices, numEdges, numImportantVertices;
vector<int> importantVertices;
vector<vector<long long> > dp;
vector<vector<pair<int,int> > > adj;

void init() {
    //freopen(".inp","r",stdin);
    //freopen(".out","w",stdout);
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
}

void Read() {
    cin >> numVertices >> numImportantVertices >> numEdges;

    importantVertices.resize(numImportantVertices);
    adj.resize(numVertices);

    for (int numImportantVertice = 0; numImportantVertice < numImportantVertices; ++numImportantVertice) {
        cin >> importantVertices[numImportantVertice];
        --importantVertices[numImportantVertice];
    }

    for (int edge = 0; edge < numEdges; ++edge) {
        int u,v,w; cin >> u >> v >> w;
        --u; --v;
        
        adj[u].emplace_back(w, v);
        adj[v].emplace_back(w, u);
    }
}

void calculate() {
    auto modifyMin = [&] (long long &x, long long y) {
        if (x > y) x = y;
    };

    dp.resize(1 << numImportantVertices);
    for (int maskOfImportantVertice = 0; maskOfImportantVertice < (1 << numImportantVertices); ++maskOfImportantVertice)
        dp[maskOfImportantVertice].resize(numVertices, (long long) 1e18);
    
    for (int numImportantVertice = 0; numImportantVertice < numImportantVertices; ++numImportantVertice) {
        int gatherVertice = importantVertices[numImportantVertice];
        dp[1<<numImportantVertice][gatherVertice] = 0;
    }

    for (int maskOfImportantVertice = 1; maskOfImportantVertice < (1 << numImportantVertices); ++maskOfImportantVertice) {
        if (bp(maskOfImportantVertice) > 1) {
            for (int gatherVertice = 0; gatherVertice < numVertices; ++gatherVertice) {
                for (int subMaskOfImportantVertice = maskOfImportantVertice; subMaskOfImportantVertice > 0; subMaskOfImportantVertice = (subMaskOfImportantVertice-1) & maskOfImportantVertice) {
                    int remainMaskOfImportantVertice = maskOfImportantVertice ^ subMaskOfImportantVertice;
                    if (remainMaskOfImportantVertice == 0) continue;

                    modifyMin(dp[maskOfImportantVertice][gatherVertice], dp[subMaskOfImportantVertice][gatherVertice] + dp[remainMaskOfImportantVertice][gatherVertice]);
                }
            }
        }

        priority_queue<pair<long long,int>, vector<pair<long long,int> >, greater<pair<long long,int> > > myPrioQueue;
        for (int gatherVertice = 0; gatherVertice < numVertices; ++gatherVertice) myPrioQueue.emplace(dp[maskOfImportantVertice][gatherVertice], gatherVertice);

        while (!myPrioQueue.empty()) {
            auto [distance, gatherVertice] = myPrioQueue.top(); myPrioQueue.pop();
            if (dp[maskOfImportantVertice][gatherVertice] != distance) continue;

            for (auto [weight, newGatherVertice]:adj[gatherVertice])
                if (dp[maskOfImportantVertice][newGatherVertice] > distance + weight) {
                    dp[maskOfImportantVertice][newGatherVertice] = distance + weight;
                    myPrioQueue.emplace(dp[maskOfImportantVertice][newGatherVertice], newGatherVertice);
                }
        }
    }
}

void printAnswer() {
    auto modifyMin = [&] (long long &x, long long y) {
        if (x > y) x = y;
    };

    long long result = (long long) 1e18;
    for (int gatherVertice = 0; gatherVertice < numVertices; ++gatherVertice)
        modifyMin(result, dp[(1<<numImportantVertices)-1][gatherVertice]);
    
    cout << result <<'\n';
}

int main() {
    init();
    Read();

    calculate();

    printAnswer();
    return 0;
}

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