oj.uz

Submission #84258

# Submission time Handle Problem Language Result Execution time Memory
84258 2018-11-14T03:47:07 Z Flying_dragon_02 Cities (BOI16_cities) C++14
74 / 100
 4347 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;
long long ans = LLONG_MAX;

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)
            ans = min(ans, f[frt.se.fi][frt.se.se]);
        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}});
                }
            }
        }
    }
    cout << ans << "\n";
}

Compilation message

cities.cpp: In function 'int main()':
cities.cpp:60:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0; i < graph[u].size(); i++) {
                        ~~^~~~~~~~~~~~~~~~~
cities.cpp:62: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 5 ms 2680 KB Output is correct
2 Correct 4 ms 2872 KB Output is correct
3 Correct 4 ms 2872 KB Output is correct
4 Correct 4 ms 2912 KB Output is correct
5 Correct 4 ms 2912 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1469 ms 50776 KB Output is correct
2 Correct 1261 ms 50776 KB Output is correct
3 Correct 668 ms 50776 KB Output is correct
4 Correct 146 ms 50776 KB Output is correct
5 Correct 538 ms 50776 KB Output is correct
6 Correct 96 ms 50776 KB Output is correct
7 Correct 9 ms 50776 KB Output is correct
8 Correct 6 ms 50776 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 50776 KB Output is correct
2 Correct 16 ms 50776 KB Output is correct
3 Correct 11 ms 50776 KB Output is correct
4 Correct 13 ms 50776 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4347 ms 100276 KB Output is correct
2 Correct 3930 ms 100276 KB Output is correct
3 Correct 2017 ms 100276 KB Output is correct
4 Correct 3052 ms 100276 KB Output is correct
5 Correct 656 ms 100276 KB Output is correct
6 Correct 247 ms 100276 KB Output is correct

Subtask #5
0 / 26.0

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