Submission #559931

#	Time	Username	Problem	Language	Result	Execution time	Memory
559931		messiuuuuu	Cities (BOI16_cities)	C++14	100 / 100	1996 ms	44720 KiB

cities

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