oj.uz

Submission #361582

# Submission time Handle Problem Language Result Execution time Memory
361582 2021-01-30T16:32:11 Z Lam_lai_cuoc_doi Cities (BOI16_cities) C++17
100 / 100
 2019 ms 39312 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;

const bool typetest = 0;
const int N = 1e5 + 5;
const ll Inf = 1e17;
int n, m, k;
int v[5];
ll d[5][N], dp[1 << 5], d2[5][5][N];
vector<pair<int, ll>> adj[N];

void Read()
{
    cin >> n >> k >> m;
    for (int i = 0; i < k; ++i)
        cin >> v[i];
    for (int i = 1; i <= m; ++i)
    {
        int u, v;
        ll w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
}

bool Relax(ll d[N], int son, int par, ll w)
{
    if (d[son] > d[par] + w)
    {
        d[son] = d[par] + w;
        return true;
    }
    return false;
}

void Dijkstra(int x, ll d[N])
{
    fill_n(&d[0], N, Inf);
    d[x] = 0;
    struct Tque
    {
        int v;
        ll w;
        Tque(const int &v = 0, const ll &w = 0) : v(v), w(w) {}
        bool operator<(const Tque &a) const
        {
            return w > a.w;
        }
    };
    priority_queue<Tque> s;
    s.emplace(x, 0);
    while (s.size())
    {
        Tque c = s.top();
        s.pop();
        if (c.w != d[c.v])
            continue;
        for (auto i : adj[c.v])
            if (Relax(d, i.first, c.v, i.second))
                s.emplace(i.first, d[i.first]);
    }
}

void Dijkstra2(int i, int j)
{
    struct Tque
    {
        int v;
        ll w;
        Tque(const int &v = 0, const ll &w = 0) : v(v), w(w) {}
        bool operator<(const Tque &a) const
        {
            return w > a.w;
        }
    };
    priority_queue<Tque> s;
    for (int x = 1; x <= n; ++x)
    {
        d2[i][j][x] = d[i][x] + d[j][x];
        s.emplace(x, d2[i][j][x]);
    }
    while (s.size())
    {
        Tque c = s.top();
        s.pop();
        if (d2[i][j][c.v] != c.w)
            continue;
        for (auto u : adj[c.v])
            if (d2[i][j][u.first] > c.w + u.second)
            {
                d2[i][j][u.first] = c.w + u.second;
                s.emplace(u.first, c.w + u.second);
            }
    }
}

void Solve()
{
    for (int i = 0; i < k; ++i)
        Dijkstra(v[i], d[i]);
    if (k == 2)
        cout << d[0][v[1]];
    else if (k == 3)
    {
        ll ans(Inf);
        for (int i = 1; i <= n; ++i)
            ans = min(ans, d[0][i] + d[1][i] + d[2][i]);
        cout << ans;
    }
    else
    {
        for (int i = 0; i < k; ++i)
            for (int j = 0; j < k; ++j)
                if (i != j)
                    Dijkstra2(i, j);
        int a[] = {0, 1, 2, 3, 4};
        ll ans(Inf);
        do
        {
            for (int i = 1; i <= n; ++i)
                ans = min(ans, d2[a[0]][a[1]][i] + d2[a[2]][a[3]][i] + (k == 5 ? d[a[4]][i] : 0));
        } while (next_permutation(a, a + k));
        cout << ans;
    }
}

int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t(1);
    if (typetest)
        cin >> t;
    for (int _ = 1; _ <= t; ++_)
    {
        Read();
        Solve();
    }
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4204 KB Output is correct
2 Correct 3 ms 4352 KB Output is correct
3 Correct 4 ms 5120 KB Output is correct
4 Correct 4 ms 5868 KB Output is correct
5 Correct 4 ms 6764 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 295 ms 17276 KB Output is correct
2 Correct 270 ms 17848 KB Output is correct
3 Correct 127 ms 10348 KB Output is correct
4 Correct 73 ms 14036 KB Output is correct
5 Correct 233 ms 16516 KB Output is correct
6 Correct 80 ms 13344 KB Output is correct
7 Correct 5 ms 5228 KB Output is correct
8 Correct 4 ms 4460 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6124 KB Output is correct
2 Correct 8 ms 6124 KB Output is correct
3 Correct 6 ms 6124 KB Output is correct
4 Correct 6 ms 6124 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1332 ms 32096 KB Output is correct
2 Correct 1318 ms 31448 KB Output is correct
3 Correct 841 ms 24292 KB Output is correct
4 Correct 704 ms 24884 KB Output is correct
5 Correct 186 ms 16464 KB Output is correct
6 Correct 84 ms 17260 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2009 ms 39312 KB Output is correct
2 Correct 2019 ms 39140 KB Output is correct
3 Correct 2015 ms 38496 KB Output is correct
4 Correct 1243 ms 31300 KB Output is correct
5 Correct 1044 ms 28560 KB Output is correct
6 Correct 286 ms 18048 KB Output is correct
7 Correct 93 ms 18284 KB Output is correct