Submission #1111153

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111153		Ghulam_Junaid	Cities (BOI16_cities)	C++17	14 / 100	2510 ms	132928 KiB

cities

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<ll, ll> pii;
 
const ll N = 2e5 + 10;
const ll inf = 1e18 + 7;
 
ll n, k, m, dist[100][N], dp[N][100], best[100];
vector<ll> special;
vector<pii> g[N];
map<int, int> id;
 
void dijkstra(ll sp, ll source){
    for (ll i = 1; i <= n; i ++)
        dist[sp][i] = inf;
    dist[sp][source] = 0;
 
    set<pair<ll, ll>> left;
    left.insert({0, source});
 
    while (left.size()){
        ll v = (*left.begin()).second;
        left.erase(left.begin());
 
        for (auto [w, u] : g[v]){
            if (dist[sp][u] > dist[sp][v] + w){
                left.erase({dist[sp][u], u});
                dist[sp][u] = dist[sp][v] + w;
                left.insert({dist[sp][u], u});
            }
        }
    }
}
 
int main(){
    memset(best, -1, sizeof best);
    
    cin >> n >> k >> m;
    for (ll i = 0; i < k; i ++){
        ll v;
        cin >> v;
        special.push_back(v);
    }
    for (ll i = 0; i < m; i ++){
        ll u, v, w;
        cin >> u >> v >> w;
        g[u].push_back({w, v});
        g[v].push_back({w, u});
    }
 
    for (ll i = 0; i < k; i ++)
        dijkstra(i, special[i]);
 
    ll ans = inf;
    for (ll v = 1; v <= n; v ++){
        for (ll mask = 1; mask < (1 << k); mask ++){
            vector<ll> vec;
            for (ll i = 0; i < k; i ++)
                if ((1 << i) & mask)
                    vec.push_back(i);
 
            dp[v][mask] = inf;
 
            ll sz = vec.size();
            do
            {
                ll cur = dist[vec[0]][v];
                for (ll i = 1; i < sz; i ++)
                    cur += dist[vec[i - 1]][special[vec[i]]];
                dp[v][mask] = min(dp[v][mask], cur);
            } while (next_permutation(vec.begin(), vec.end()));
        
            for (int submask = mask; submask != 0; submask = (submask - 1) & mask)
                dp[v][mask] = min(dp[v][mask], dp[v][submask] + dp[v][mask ^ submask]);
 
            if (best[mask] == -1 or dp[best[mask]][mask] > dp[v][mask])
                best[mask] = v;
            if (mask == (1 << k) - 1)
                ans = min(ans, dp[v][mask]);
        }
    }
 
    int cur = k;
    for (int mask = 1; mask < ((1 << k) - 1); mask ++){
        int comp = ((1 << k) - 1) ^ mask;
 
        int u = best[mask];
        int v = best[comp];
 
        dijkstra(cur, u);
        ans = min(ans, dp[u][mask] + dist[cur][v] + dp[v][comp]);
        cur++;
    }
 
    cout << ans << endl;
}

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