oj.uz

Submission #97508

# Submission time Handle Problem Language Result Execution time Memory
97508 2019-02-16T13:22:24 Z minhtung0404 Cities (BOI16_cities) C++17
100 / 100
 5105 ms 48436 KB 
//https://oj.uz/problem/view/BOI16_cities

#include<bits/stdc++.h>
const int N = 1e5 + 5;
const long long inf = 1e18;
using namespace std;

typedef pair <long long, int> ii;
vector <ii> G[N];
int n, k, m;
long long f[N][32], ans = inf, a[5];

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    for (int i = 0; i < N; i++) for (int j = 0; j < 32; j++) f[i][j] = inf;
    cin >> n >> k >> m;
    for (int i = 0; i < k; i++) {
        cin >> a[i];
        f[a[i]][1 << i] = 0;
    }
    while (m--){
        int u, v, c; cin >> u >> v >> c;
        G[u].push_back(ii(c, v));
        G[v].push_back(ii(c, u));
    }
    for (int mask = 1; mask < (1 << k); mask++){
        priority_queue <ii, vector <ii>, greater <ii> > mq;
        for (int i = 0; i < mask; i++){
            if ((mask | i) != mask) continue;
            int a = i ^ mask;
            if (i < a) continue;
            for (int j = 1; j <= n; j++) f[j][mask] = min(f[j][mask], f[j][i] + f[j][a]);
        }
        for (int i = 1; i <= n; i++) if (f[i][mask] != inf) mq.push(ii(f[i][mask], i));
        while (mq.size()){
            int u = mq.top().second; long long c = mq.top().first; mq.pop();
            if (c != f[u][mask]) continue;
            for (auto p : G[u]){
                int v = p.second, cost = p.first;
                if (f[v][mask] > f[u][mask] + cost){
                    f[v][mask] = f[u][mask] + cost;
                    mq.push(ii(f[v][mask], v));
                }
            }
        }
    }
    for (int i = 1; i <= n; i++) ans = min(ans, f[i][(1 << k) - 1]);
    cout << ans;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 27768 KB Output is correct
2 Correct 30 ms 27776 KB Output is correct
3 Correct 28 ms 27776 KB Output is correct
4 Correct 24 ms 27776 KB Output is correct
5 Correct 26 ms 27748 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1193 ms 44592 KB Output is correct
2 Correct 1122 ms 44236 KB Output is correct
3 Correct 720 ms 36888 KB Output is correct
4 Correct 185 ms 36564 KB Output is correct
5 Correct 634 ms 42360 KB Output is correct
6 Correct 143 ms 36780 KB Output is correct
7 Correct 28 ms 27896 KB Output is correct
8 Correct 25 ms 27904 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 27980 KB Output is correct
2 Correct 34 ms 27904 KB Output is correct
3 Correct 32 ms 27768 KB Output is correct
4 Correct 30 ms 27904 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2430 ms 44624 KB Output is correct
2 Correct 2396 ms 44088 KB Output is correct
3 Correct 1544 ms 36736 KB Output is correct
4 Correct 1355 ms 41888 KB Output is correct
5 Correct 363 ms 37740 KB Output is correct
6 Correct 163 ms 38936 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 5105 ms 44824 KB Output is correct
2 Correct 4944 ms 44740 KB Output is correct
3 Correct 4804 ms 48436 KB Output is correct
4 Correct 3559 ms 39088 KB Output is correct
5 Correct 2614 ms 45968 KB Output is correct
6 Correct 605 ms 41604 KB Output is correct
7 Correct 240 ms 42416 KB Output is correct