oj.uz

Submission #1111153

# Submission time Handle Problem Language Result Execution time Memory
1111153 2024-11-11T15:26:32 Z Ghulam_Junaid Cities (BOI16_cities) C++17
14 / 100
 2510 ms 132928 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 13136 KB Output is correct
2 Correct 3 ms 12880 KB Output is correct
3 Correct 3 ms 12880 KB Output is correct
4 Incorrect 3 ms 12880 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 761 ms 109888 KB Output is correct
2 Correct 733 ms 112132 KB Output is correct
3 Correct 231 ms 101192 KB Output is correct
4 Correct 124 ms 31492 KB Output is correct
5 Correct 518 ms 105864 KB Output is correct
6 Correct 125 ms 23112 KB Output is correct
7 Correct 6 ms 11088 KB Output is correct
8 Correct 5 ms 10832 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 9040 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 1327 ms 118288 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 2510 ms 132928 KB Output isn't correct
2 Halted 0 ms 0 KB -