oj.uz

Submission #84260

# Submission time Handle Problem Language Result Execution time Memory
84260 2018-11-14T03:50:18 Z Flying_dragon_02 Cities (BOI16_cities) C++14
74 / 100
 3274 ms 263168 KB 
#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define pb push_back
#define mp make_pair

typedef pair<int, int> ii;

const int N = 1e5 + 5;

long long f[N][(1 << 5)];

int n, k, m;

vector<int> vec[(1 << 5)];
typedef pair<long long, ii> pii;

priority_queue<pii, vector<pii>, greater<pii>> pq;

vector<ii> graph[N];

int main() {
    cin.tie(0), ios::sync_with_stdio(0);
    cin >> n >> k >> m;
    for(int mask1 = 0; mask1 < (1 << k); mask1++) {
        for(int mask2 = 0; mask2 < (1 << k); mask2++) {
            if(!(mask1 & mask2))
                vec[mask1].pb(mask2);
        }
    }
    for(int i = 1; i <= n; i++) {
        for(int j = 0; j < (1 << k); j++)
            f[i][j] = LLONG_MAX;
    }
    for(int i = 1; i <= n; i++)
        f[i][0] = 0;
    for(int i = 1; i <= k; i++) {
        int x;
        cin >> x;
        f[x][(1 << (i - 1))] = 0;
        pq.push({0, {x, (1 << (i - 1))}});
    }
    for(int i = 1; i <= m; i++) {
        int u, v, c;
        cin >> u >> v >> c;
        graph[u].pb({v, c});
        graph[v].pb({u, c});
    }
    while(!pq.empty()) {
        pii frt = pq.top();
        pq.pop();
        if(frt.se.se == (1 << k) - 1) {
            cout << f[frt.se.fi][frt.se.se];
            exit(0);
        }
        int u = frt.se.fi, mask = frt.se.se;
        if(frt.fi > f[u][mask]) continue;
        for(int i = 0; i < graph[u].size(); i++) {
            int v = graph[u][i].fi, w = graph[u][i].se;
            for(int j = 0; j < vec[mask].size(); j++) {
                int nmask = vec[mask][j], newmask = (mask | nmask);
                if(f[v][nmask] == LLONG_MAX) continue;
                if(f[v][newmask] > f[u][mask] + w + f[v][nmask]) {
                    f[v][newmask] = f[u][mask] + w + f[v][nmask];
                    pq.push({f[v][newmask], {v, newmask}});
                }
                if(f[u][newmask] > f[u][mask] + w + f[v][nmask]) {
                    f[u][newmask] = f[u][mask] + w + f[v][nmask];
                    pq.push({f[u][newmask], {u, newmask}});
                }
            }
        }
    }
}

Compilation message

cities.cpp: In function 'int main()':
cities.cpp:61:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0; i < graph[u].size(); i++) {
                        ~~^~~~~~~~~~~~~~~~~
cities.cpp:63:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j = 0; j < vec[mask].size(); j++) {
                            ~~^~~~~~~~~~~~~~~~~~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2848 KB Output is correct
3 Correct 4 ms 2848 KB Output is correct
4 Correct 5 ms 2848 KB Output is correct
5 Correct 5 ms 2848 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 797 ms 51128 KB Output is correct
2 Correct 817 ms 51128 KB Output is correct
3 Correct 172 ms 51128 KB Output is correct
4 Correct 131 ms 51128 KB Output is correct
5 Correct 341 ms 51128 KB Output is correct
6 Correct 86 ms 51128 KB Output is correct
7 Correct 8 ms 51128 KB Output is correct
8 Correct 6 ms 51128 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 51128 KB Output is correct
2 Correct 14 ms 51128 KB Output is correct
3 Correct 9 ms 51128 KB Output is correct
4 Correct 11 ms 51128 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3274 ms 100644 KB Output is correct
2 Correct 2717 ms 100744 KB Output is correct
3 Correct 1357 ms 100744 KB Output is correct
4 Correct 2091 ms 100744 KB Output is correct
5 Correct 444 ms 100744 KB Output is correct
6 Correct 237 ms 100744 KB Output is correct

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Runtime error 2372 ms 263168 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -