oj.uz

Submission #97500

# Submission time Handle Problem Language Result Execution time Memory
97500 2019-02-16T13:03:58 Z minhtung0404 Cities (BOI16_cities) C++17
74 / 100
 4872 ms 49116 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[10];

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 = 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 = 0; i < k; i++) if (!((mask >> i)&1)) f[u][mask | (1 << i)] = min(f[u][mask | (1 << i)], f[u][1 << i] + f[u][mask]);
        }
    }
    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 27896 KB Output is correct
2 Correct 25 ms 27768 KB Output is correct
3 Correct 25 ms 27768 KB Output is correct
4 Correct 29 ms 27768 KB Output is correct
5 Correct 26 ms 27768 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1248 ms 49080 KB Output is correct
2 Correct 1177 ms 48376 KB Output is correct
3 Correct 690 ms 38996 KB Output is correct
4 Correct 154 ms 40240 KB Output is correct
5 Correct 614 ms 46792 KB Output is correct
6 Correct 125 ms 40172 KB Output is correct
7 Correct 27 ms 27900 KB Output is correct
8 Correct 26 ms 27896 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 27896 KB Output is correct
2 Correct 34 ms 27900 KB Output is correct
3 Correct 30 ms 27776 KB Output is correct
4 Correct 37 ms 27896 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2393 ms 49056 KB Output is correct
2 Correct 2268 ms 48448 KB Output is correct
3 Correct 1613 ms 39084 KB Output is correct
4 Correct 1288 ms 46016 KB Output is correct
5 Correct 409 ms 41732 KB Output is correct
6 Correct 214 ms 42360 KB Output is correct

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 4814 ms 49116 KB Output is correct
2 Incorrect 4872 ms 49016 KB Output isn't correct
3 Halted 0 ms 0 KB -