oj.uz

Submission #559931

# Submission time Handle Problem Language Result Execution time Memory
559931 2022-05-11T01:13:39 Z messiuuuuu Cities (BOI16_cities) C++14
100 / 100
 1996 ms 44720 KB 
#include <bits/stdc++.h>
#define task "CITIES"
#define ll long long
#define ld long double
#define fi first
#define se second
#define pb push_back
using namespace std;
const int MAXN = 1e5 + 5;
const ll INF = 1e18 + 5;

int n, k, m;
int imp[6];
vector<pair<int, int>> Adj[MAXN];

void Input()
{
    cin >> n >> k >> m;
    for (int i = 1; i <= k; i++)
        cin >> imp[i];
    while (m-- > 0)
    {
        int u, v, w;
        cin >> u >> v >> w;
        Adj[u].pb({v, w});
        Adj[v].pb({u, w});
    }
}

ll dp[1 << 5][MAXN];
int tmsk;

struct TReq
{
    int u;
    ll dlab;
    bool operator < (const TReq& other) const
    {
        return dlab > other.dlab;
    }
    bool Valid() const
    {
        return dlab == dp[tmsk][u];
    }
};

void Solve()
{
    for (int i = 0; i < (1 << k); i++)
        fill(dp[i], dp[i] + 1 + n, INF);
    for (int i = 1; i <= k; i++)
    {
        dp[1 << (i - 1)][imp[i]] = 0;
    }
    for (int mask = 1; mask < (1 << k); mask++)
    {
        tmsk = mask;
        for (int mask1 = 0; mask1 < mask; mask1++)
        {
            if ((mask1 | mask) != mask)
                continue;
            int mask2 = mask ^ mask1;
            if (mask2 < mask1)
                continue;
            for (int u = 1; u <= n; u++)
                dp[mask][u] = min(dp[mask][u], dp[mask1][u] + dp[mask2][u]);
        }

        priority_queue<TReq> PQ;
        for (int i = 1; i <= n; i++)
            if (dp[mask][i] < INF)
                PQ.push({i, dp[mask][i]});

        while (!PQ.empty())
        {
            auto c = PQ.top();
            PQ.pop();
            if (!c.Valid())
                continue;
            for (auto v : Adj[c.u])
            {
                if (dp[mask][v.fi] > c.dlab + v.se)
                {
                    dp[mask][v.fi] = c.dlab + v.se;
                    PQ.push({v.fi, dp[mask][v.fi] = c.dlab + v.se});
                }
            }
        }
    }
    ll ans = INF;
    for (int i = 1; i <= n; i++)
        ans = min(ans, dp[(1 << k) - 1][i]);
    cout << ans;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    //freopen(taskname".INP" , "r" , stdin);
    //freopen(taskname".OUT" , "w" , stdout);
    Input();
    Solve();
    return 0;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2676 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2772 KB Output is correct
5 Correct 2 ms 2772 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 448 ms 25848 KB Output is correct
2 Correct 534 ms 25648 KB Output is correct
3 Correct 281 ms 17756 KB Output is correct
4 Correct 82 ms 10896 KB Output is correct
5 Correct 252 ms 20384 KB Output is correct
6 Correct 59 ms 10864 KB Output is correct
7 Correct 4 ms 2900 KB Output is correct
8 Correct 3 ms 2816 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3028 KB Output is correct
2 Correct 7 ms 3044 KB Output is correct
3 Correct 4 ms 2900 KB Output is correct
4 Correct 4 ms 2900 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 998 ms 29772 KB Output is correct
2 Correct 966 ms 31916 KB Output is correct
3 Correct 548 ms 24168 KB Output is correct
4 Correct 570 ms 22608 KB Output is correct
5 Correct 139 ms 13512 KB Output is correct
6 Correct 67 ms 12536 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1958 ms 44720 KB Output is correct
2 Correct 1969 ms 44612 KB Output is correct
3 Correct 1996 ms 44632 KB Output is correct
4 Correct 1208 ms 36752 KB Output is correct
5 Correct 966 ms 28784 KB Output is correct
6 Correct 221 ms 14816 KB Output is correct
7 Correct 71 ms 12688 KB Output is correct