oj.uz

Submission #723401

# Submission time Handle Problem Language Result Execution time Memory
723401 2023-04-13T17:31:46 Z _martynas Cities (BOI16_cities) C++11
100 / 100
 1932 ms 70008 KB 
#include <bits/stdc++.h>

using namespace std;

#define F first
#define S second
#define PB push_back

using ll = long long;
using pii = pair<int, int>;

const int MXN = 2e5+5;
const ll INF = 1e16;

int n, k, m;
int important[MXN];
vector<pii> adj[MXN];
ll dp[32][MXN];
bool visited[MXN];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> k >> m;
    for(int i = 0; i < k; i++) cin >> important[i];
    for(int i = 0; i < m; i++) {
        int a, b, c; cin >> a >> b >> c;
        adj[a].PB({b, c}), adj[b].PB({a, c});
    }
    fill((ll*)dp, (ll*)dp+32*MXN, INF);
    for(int i = 0; i < k; i++) dp[1<<i][important[i]] = 0;
    priority_queue<pair<ll, int>> PQ;
    for(int mask = 1; mask < (1<<k); mask++) {
        for(int subset = 0; subset < mask; subset++) {
            if((subset | mask) != mask) continue;
            for(int i = 1; i <= n; i++) dp[mask][i] = min(dp[mask][i], dp[subset][i]+dp[subset^mask][i]);
        }
        memset(visited, 0, sizeof(visited));
        for(int i = 1; i <= n; i++) if(dp[mask][i] < INF) PQ.push({-dp[mask][i], i});
        while(!PQ.empty()) {
            ll cost = -PQ.top().F;
            int i = PQ.top().S;
            PQ.pop();
            if(visited[i]) continue;
            visited[i] = true;
            for(auto e : adj[i]) {
                if(visited[e.F]) continue;
                if(dp[mask][e.F] > cost+e.S) {
                    dp[mask][e.F] = cost+e.S;
                    PQ.push({-dp[mask][e.F], e.F});
                }
            }
        }
    }
    cout << *min_element(dp[(1<<k)-1]+1, dp[(1<<k)-1]+n+1);
    return 0;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 55208 KB Output is correct
2 Correct 23 ms 55236 KB Output is correct
3 Correct 22 ms 55216 KB Output is correct
4 Correct 23 ms 55200 KB Output is correct
5 Correct 23 ms 55300 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 520 ms 69944 KB Output is correct
2 Correct 468 ms 69608 KB Output is correct
3 Correct 287 ms 62656 KB Output is correct
4 Correct 89 ms 63392 KB Output is correct
5 Correct 293 ms 70008 KB Output is correct
6 Correct 86 ms 63384 KB Output is correct
7 Correct 25 ms 55372 KB Output is correct
8 Correct 26 ms 55396 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 55368 KB Output is correct
2 Correct 27 ms 55484 KB Output is correct
3 Correct 27 ms 55372 KB Output is correct
4 Correct 27 ms 55380 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1025 ms 69952 KB Output is correct
2 Correct 898 ms 69600 KB Output is correct
3 Correct 584 ms 62720 KB Output is correct
4 Correct 577 ms 67384 KB Output is correct
5 Correct 188 ms 64400 KB Output is correct
6 Correct 102 ms 65016 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1932 ms 69984 KB Output is correct
2 Correct 1778 ms 70004 KB Output is correct
3 Correct 1873 ms 69748 KB Output is correct
4 Correct 1355 ms 62724 KB Output is correct
5 Correct 1032 ms 67388 KB Output is correct
6 Correct 248 ms 64428 KB Output is correct
7 Correct 127 ms 64972 KB Output is correct