oj.uz

Submission #709940

# Submission time Handle Problem Language Result Execution time Memory
709940 2023-03-14T21:56:31 Z noedit Cities (BOI16_cities) C++17
100 / 100
 5021 ms 44384 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

using namespace std;

const int INF = 1e9;
typedef long long ll;
const ll INFLL = 1e18;

const int MAXN = 2e5;
const int MAXK = 5;
const int MAXMSK = 32;
ll dp[MAXMSK][MAXN];
vector<vector<pair<int, int> > > g;

signed main()
{
    //ifstream cin("input.txt");
    //ofstream cout("output.txt");
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, k, m;
    cin >> n >> k >> m;
    g.resize(n);
    vector<int> a(k);
    for (int i = 0; i < k; i++) cin >> a[i];
    for (int i = 0; i < m; i++)
    {
        int x, y, z;
        cin >> x >> y >> z;
        x--; y--;
        g[x].push_back({y, z});
        g[y].push_back({x, z});
    }
    for (int i = 0; i < MAXMSK; i++) for (int j = 0; j < n; j++) dp[i][j] = INFLL;
    for (int i = 0; i < k; i++)
    {
        dp[1 << i][a[i] - 1] = 0;
    }
    for (int mask = 1; mask < (1 << k); mask++)
    {
        for (int sub1 = mask; sub1; sub1 = (sub1 - 1) & mask)
        {
            int sub2 = mask ^ sub1;
            for (int v = 0; v < n; v++)
            dp[mask][v] = min(dp[mask][v], dp[sub1][v] + dp[sub2][v]);
        }
        set<pair<ll, int> > st;
        for (int v = 0; v < n; v++)
        {
            if (dp[mask][v] == INFLL) continue;
            st.insert({dp[mask][v], v});
        }
        while (!st.empty())
        {
            auto [d, v] = *st.begin();
            st.erase(st.begin());
            for (auto&[u, w] : g[v])
            {
                if (dp[mask][u] > d + w)
                {
                    st.erase({dp[mask][u], u});
                    dp[mask][u] = d + w;
                    st.insert({dp[mask][u], u});
                }
            }
        }
    }
    ll ans = INFLL;
//    for (int i = 0; i < (1 << k); i++){
//            cout << i << endl;
//        for (int j = 0; j < n; j++)
//        cout << dp[i][j] << " ";
//    cout << endl;
//    }
    for (int i = 0; i < n; i++)
    {
        ans = min(ans, dp[(1 << k) - 1][i]);
    }
    cout << ans;
    return 0;
}
/*
4 3 6
1 3 4
1 2 4
1 3 9
1 4 6
2 3 2
2 4 5
3 4 8
*/

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 2 ms 452 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1142 ms 44384 KB Output is correct
2 Correct 957 ms 44276 KB Output is correct
3 Correct 396 ms 39312 KB Output is correct
4 Correct 68 ms 8652 KB Output is correct
5 Correct 395 ms 44364 KB Output is correct
6 Correct 59 ms 8644 KB Output is correct
7 Correct 6 ms 980 KB Output is correct
8 Correct 2 ms 980 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 980 KB Output is correct
2 Correct 8 ms 988 KB Output is correct
3 Correct 5 ms 852 KB Output is correct
4 Correct 5 ms 808 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2278 ms 44364 KB Output is correct
2 Correct 2185 ms 44132 KB Output is correct
3 Correct 1088 ms 39372 KB Output is correct
4 Correct 1055 ms 26996 KB Output is correct
5 Correct 253 ms 12224 KB Output is correct
6 Correct 70 ms 10368 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 4620 ms 44368 KB Output is correct
2 Correct 5021 ms 44348 KB Output is correct
3 Correct 4968 ms 44160 KB Output is correct
4 Correct 2423 ms 39372 KB Output is correct
5 Correct 2158 ms 26988 KB Output is correct
6 Correct 389 ms 12276 KB Output is correct
7 Correct 97 ms 10316 KB Output is correct