oj.uz

Submission #993859

# Submission time Handle Problem Language Result Execution time Memory
993859 2024-06-06T15:17:09 Z browntoad Cities (BOI16_cities) C++14
100 / 100
 811 ms 37168 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast", "unroll-loops")
using namespace std;
#define ll long long
#define int ll
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define REP1(i, n) FOR(i, 1, n+1)
#define RREP(i, n) for (int i = (n)-1; i >= 0; i--)
#define pii pair<int, int>
#define f first
#define s second
#define SZ(x) (int)((x).size())
#define ALL(x) (x).begin(), (x).end()
#define pb push_back
#define endl '\n'
#define IOS() ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)

const ll maxn = 1e5+5;
const ll inf = 1ll<<60;

int n, m, k;
vector<vector<int>> kdis(5);
vector<int> tod;
vector<pii> g[maxn];


vector<int> ddis(maxn); // dijkstra distance
vector<int> tmpdis(maxn);
vector<int> occ(maxn);

int trident[5][5][maxn];
void dij(){
    // initialize ddis before hand
    REP1(i, n) occ[i] = 0;
    priority_queue<pii, vector<pii>, greater<pii> > pq;
    //pq.push({ddis[i], a});
    REP1(i, n) pq.push({ddis[i], i});
    while(SZ(pq)){
        pii tp = pq.top(); pq.pop();
        if (occ[tp.s]) continue;
        occ[tp.s] = 1;
        for (auto e:g[tp.s]){
            if (!occ[e.f] && ddis[e.f] > ddis[tp.s]+e.s){
                ddis[e.f] = ddis[tp.s]+e.s;
                pq.push({ddis[e.f], e.f});
            }
        }
    }
}
void inp(){
    cin>>n>>k>>m;
    tod = vector<int> (k);
    REP(i, k) cin>>tod[i];
    REP(i, m){
        int u, v, c; cin>>u>>v>>c;
        g[u].pb({v, c});
        g[v].pb({u, c});
    }
}

const vector<vector<int>> four = {{0, 1, 2, 3}, {0, 2, 1, 3}, {0, 3, 1, 2}, {1, 2, 0, 3}, {1, 3, 0, 2}, {2, 3, 0, 1}};
//vector<vector<int>> four = {{0, 2, 1, 3}};
const vector<vector<int>> five1 = {{0, 1, 2, 3, 4},
{0, 1, 3, 2, 4},
{0, 1, 4, 2, 3},
{0, 2, 3, 1, 4},
{0, 2, 4, 1, 3},
{0, 3, 4, 1, 2},
{1, 0, 2, 3, 4},
{1, 0, 3, 2, 4},
{1, 0, 4, 2, 3},
{1, 2, 3, 0, 4},
{1, 2, 4, 0, 3},
{1, 3, 4, 0, 2},
{2, 0, 1, 3, 4},
{2, 0, 3, 1, 4},
{2, 0, 4, 1, 3},
{2, 1, 3, 0, 4},
{2, 1, 4, 0, 3},
{2, 3, 4, 0, 1},
{3, 0, 1, 2, 4},
{3, 0, 2, 1, 4},
{3, 0, 4, 1, 2},
{3, 1, 2, 0, 4},
{3, 1, 4, 0, 2},
{3, 2, 4, 0, 1},
{4, 0, 1, 2, 3},
{4, 0, 2, 1, 3},
{4, 0, 3, 1, 2},
{4, 1, 2, 0, 3},
{4, 1, 3, 0, 2},
{4, 2, 3, 0, 1}
};

const vector<vector<int>> five2 = {{0, 1, 2, 3, 4},
{0, 2, 1, 3, 4},
{0, 3, 1, 2, 4},
{0, 4, 1, 2, 3},
{1, 2, 0, 3, 4},
{1, 3, 0, 2, 4},
{1, 4, 0, 2, 3},
{2, 3, 0, 1, 4},
{2, 4, 0, 1, 3},
{3, 4, 0, 1, 2}
};
signed main(){
    IOS();
    inp();
    REP(i, k){
        fill(ALL(ddis), inf);
        ddis[tod[i]] = 0;
        dij();
        kdis[i] = ddis;
    }
    REP(i, k){
        FOR(j, i+1, k){
            REP1(l, n){
                ddis[l] = kdis[i][l] + kdis[j][l];
            }
            dij();
            REP1(l, n) trident[i][j][l] = ddis[l];
        }
    }

    vector<int> dp(1<<k);
    REP(i, (1<<k)){
        int bb = __builtin_popcount(i);
        if (bb <= 1) continue;
        else{
            vector<int> ids; // actual indices
            REP(j, k) if (i&(1<<j)) ids.pb(j);

            dp[i] = inf;
            REP1(j, n){
                int cnt = 0;
                REP(l, k) cnt += kdis[l][j];
                dp[i] = min(dp[i], cnt);
            }

            if (bb <= 3) continue;

            for (auto j:ids){
                for (auto l:ids){
                    if (j != l) dp[i] = min(dp[i], dp[i-(1<<j)]+kdis[j][tod[l]]);
                }

            }

            if (bb == 4){
                for (auto &t:four){
                    REP1(j, n){
                        dp[i] = min(dp[i], trident[ids[t[0]]][ids[t[1]]][j] + kdis[ids[t[2]]][j] + kdis[ids[t[3]]][j]);
                    }
                }

            }
            else {
                for (auto &t:five1){
                    dp[i] = min(dp[i], dp[(1<<t[0])+(1<<t[1])+(1<<t[2])] + dp[(1<<t[0])+(1<<t[3])+(1<<t[4])]);
                }
                for (auto &t:five2){
                    REP1(j, n){
                        dp[i] = min(dp[i], trident[ids[t[0]]][ids[t[1]]][j] + kdis[ids[t[2]]][j] + kdis[ids[t[3]]][j] + kdis[ids[t[4]]][j]);
                    }
                }
                for (auto &t:five1){
                    REP1(j, n){
                        dp[i] = min(dp[i], trident[ids[t[1]]][ids[t[2]]][j] + trident[ids[t[3]]][ids[t[4]]][j] + kdis[t[0]][j]);
                    }
                }
            }

        }
    }
    cout<<dp[(1<<k)-1]<<endl;
}
/*
6 4 8
2 3 5 6
1 4 3
2 5 13
2 1 3
2 6 13
3 4 3
4 6 3
4 2 13
1 5 3
*/

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6748 KB Output is correct
2 Correct 3 ms 6748 KB Output is correct
3 Correct 3 ms 7516 KB Output is correct
4 Correct 4 ms 8284 KB Output is correct
5 Correct 4 ms 9052 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 351 ms 29928 KB Output is correct
2 Correct 359 ms 29312 KB Output is correct
3 Correct 199 ms 20056 KB Output is correct
4 Correct 50 ms 19784 KB Output is correct
5 Correct 221 ms 27504 KB Output is correct
6 Correct 49 ms 19112 KB Output is correct
7 Correct 5 ms 7768 KB Output is correct
8 Correct 4 ms 6748 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 8540 KB Output is correct
2 Correct 6 ms 8540 KB Output is correct
3 Correct 5 ms 8284 KB Output is correct
4 Correct 5 ms 8540 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 576 ms 32916 KB Output is correct
2 Correct 507 ms 32492 KB Output is correct
3 Correct 349 ms 23096 KB Output is correct
4 Correct 322 ms 28368 KB Output is correct
5 Correct 106 ms 22096 KB Output is correct
6 Correct 63 ms 22884 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 811 ms 37112 KB Output is correct
2 Correct 793 ms 37168 KB Output is correct
3 Correct 770 ms 36304 KB Output is correct
4 Correct 464 ms 26956 KB Output is correct
5 Correct 479 ms 30544 KB Output is correct
6 Correct 132 ms 23268 KB Output is correct
7 Correct 66 ms 23916 KB Output is correct