oj.uz

Submission #485815

# Submission time Handle Problem Language Result Execution time Memory
485815 2021-11-09T12:28:49 Z Rainbowbunny Cities (BOI16_cities) C++17
100 / 100
 1858 ms 47384 KB 
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e5 + 5;
const long long INF = 1e18;

int n, m, k;
long long dp[32][MAXN];
vector <pair <int, long long> > Adj[MAXN];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> k >> m;
    for(int i = 0; i < 32; i++)
    {
        for(int j = 0; j < MAXN; j++)
        {
            dp[i][j] = INF;
        }
    }
    for(int i = 0; i < k; i++)
    {
        int id;
        cin >> id;
        dp[1 << i][id] = 0;
    }
    for(int i = 1; i <= m; i++)
    {
        int u, v;
        long long c;
        cin >> u >> v >> c;
        Adj[u].emplace_back(v, c);
        Adj[v].emplace_back(u, c);
    }
    for(int i = 1; i < (1 << k); i++)
    {
        for(int mask = i; mask > 0; mask = (mask - 1) & i)
        {
            if(mask == i)
            {
                continue;
            }
            for(int j = 1; j <= n; j++)
            {
                dp[i][j] = min(dp[i][j], dp[i ^ mask][j] + dp[mask][j]);
            }
        }
        priority_queue <pair <long long, int> > pq;
        for(int j = 1; j <= n; j++)
        {
            if(dp[i][j] != INF)
            {
                pq.emplace(-dp[i][j], j);
            }
        }
        while(pq.empty() == false)
        {
            long long d = -pq.top().first, v = pq.top().second;
            pq.pop();
            if(d != dp[i][v])
            {
                continue;
            }
            for(auto x : Adj[v])
            {
                if(dp[i][x.first] > d + x.second)
                {
                    dp[i][x.first] = d + x.second;
                    pq.emplace(-dp[i][x.first], x.first);
                }
            }
        }
    }
    cout << *min_element(dp[(1 << k) - 1] + 1, dp[(1 << k) - 1] + n + 1) << '\n';
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 27596 KB Output is correct
2 Correct 11 ms 27700 KB Output is correct
3 Correct 12 ms 27596 KB Output is correct
4 Correct 11 ms 27596 KB Output is correct
5 Correct 11 ms 27704 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 435 ms 44336 KB Output is correct
2 Correct 487 ms 43856 KB Output is correct
3 Correct 237 ms 36572 KB Output is correct
4 Correct 68 ms 36740 KB Output is correct
5 Correct 276 ms 42248 KB Output is correct
6 Correct 59 ms 36676 KB Output is correct
7 Correct 12 ms 27852 KB Output is correct
8 Correct 14 ms 27768 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 27848 KB Output is correct
2 Correct 19 ms 27784 KB Output is correct
3 Correct 14 ms 27728 KB Output is correct
4 Correct 13 ms 27852 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 896 ms 44452 KB Output is correct
2 Correct 891 ms 46828 KB Output is correct
3 Correct 547 ms 38712 KB Output is correct
4 Correct 534 ms 44736 KB Output is correct
5 Correct 156 ms 40464 KB Output is correct
6 Correct 75 ms 41732 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1858 ms 44624 KB Output is correct
2 Correct 1779 ms 47384 KB Output is correct
3 Correct 1799 ms 47016 KB Output is correct
4 Correct 1309 ms 38808 KB Output is correct
5 Correct 963 ms 44692 KB Output is correct
6 Correct 232 ms 40500 KB Output is correct
7 Correct 92 ms 42040 KB Output is correct