21 Days Training // Day 1~4

ABC364_G

Ideas :
For all possible Last Major City, solve the mininum steiner tree.
Not std code :

#include 
using namespace std;

map G;
map emp;
vector Vks;
queue Q;
vector dp;
vector empV;
set vis;
long long V, E, Vk;

void relax(long long cur) {
    vis.clear();
    while (!Q.empty()) {
        pair c = Q.front();Q.pop();
        if (vis.find(c.second)!=vis.end()) continue;
        vis.insert(c.second);
        for (map::iterator it=G[c.second].begin();it!=G[c.second].end();it++) {
            if (dp[(*it).first][cur] > dp[c.second][cur] + (*it).second) {
                dp[(*it).first][cur] = dp[c.second][cur] + (*it).second;
                Q.push(make_pair(dp[(*it).first][cur], (*it).first));
            }
        }
    }
}

void init() {
    cin >> V >> E >> Vk;
    empV.resize(1< w;
        u--;v--;
        if (G.find(u)==G.end()) G[u]=emp;
        if (G.find(v)==G.end()) G[v]=emp;
        if (G.find(u)!=G.end()&&G[u].find(v)!=G[u].end()) {
            G[u][v] = min(G[u][v], w);
            G[v][u] = min(G[v][u], w);
            continue;
        }
        G[u][v] = w;
        G[v][u] = w;

    }
    for (long long i=0;i<Vk-1;i++) {
        Vks.push_back(i);
        dp[i][1<<i]=0;
    } 
    Vks.push_back(1145141919);
}
void query(int Vkl) {
    dp.clear();
    dp.resize(V);
    for (long long i=0;i<V;i++) dp[i] = empV;
    Vks[Vk-1] = Vkl;
    for (long long i=0;i<Vk-1;i++) {
        dp[i][1<<i]=0;
    } 
    dp[Vkl][1<<(Vk-1)]=0;
    for (long long cur=1;cur<(1<<Vk);cur++) {
        for (long long i=0;i<V;i++) {
            for (long long sub = cur&(cur-1);sub;sub=cur&(sub-1)) {
                dp[i][cur] = min(dp[i][cur], dp[i][sub]+dp[i][cur^sub]);
            } 
            if (dp[i][cur]!=INT_MAX) Q.push(make_pair(dp[i][cur],i));
        }
        relax(cur);
    }
    cout << dp[Vks[0]][(1<<Vk)-1] << endl;
    return ;
}
int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    init();
    for (int i=Vk-1;i<V;i++) query(i);
}