Submission #361582

#	Time	Username	Problem	Language	Result	Execution time	Memory
361582		Lam_lai_cuoc_doi	Cities (BOI16_cities)	C++17	100 / 100	2019 ms	39312 KiB

cities

#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 / 22
• Subtask 2: 14 / 14
• Subtask 3: 15 / 15
• Subtask 4: 23 / 23
• Subtask 5: 26 / 26