oj.uz

Submission #91015

# Submission time Handle Problem Language Result Execution time Memory
91015 2018-12-25T15:24:47 Z EntityIT Cities (BOI16_cities) C++14
100 / 100
 2784 ms 104820 KB 
#include<bits/stdc++.h>

using namespace std;

#define pb push_back
#define fi first
#define se second
typedef pair<int, int> ii;
typedef pair<long long, int> lli;

const int N = 1e5 + 5;
const long long inf = (long long)1e18 + 123;
int n, K, m;
long long d[1 << 5][N];
vector<int> important;
vector<ii> gr[N];

int main () {
//    freopen("test.INP", "r", stdin);
    for (int mask = 0; mask < (1 << 5); ++mask) {
        for (int i = 0; i < N; ++i) d[mask][i] = inf;
    }

    scanf("%d %d %d", &n, &K, &m);
    important.assign(K, 0);
    for (int i = 0; i < K; ++i) {
        int u; scanf("%d", &u);
        important[i] = u;
        d[1 << i][u] = 0;
    }

    while (m --) {
        int u, v, w; scanf("%d %d %d", &u, &v, &w);
        gr[u].pb(ii(v, w) );
        gr[v].pb(ii(u, w) );
    }

    for (int mask = 1; mask < (1 << K); ++mask) {
        for (int subMask = mask; subMask; subMask = (subMask - 1) & mask) {
            for (int u = 1; u <= n; ++u) d[mask][u] = min(d[mask][u], d[subMask][u] + d[mask ^ subMask][u]);
        }
        priority_queue<lli, vector<lli>, greater<lli> > pq;
        for (int u = 1; u <= n; ++u) pq.push(lli(d[mask][u], u) );
        while (!pq.empty() ) {
            lli tmp = pq.top(); pq.pop();
            int u = tmp.se;
            if (tmp.fi > d[mask][u]) continue ;
            for (ii _ : gr[u]) {
                int v = _.fi, w = _.se;
                if (d[mask][v] > d[mask][u] + w) {
                    d[mask][v] = d[mask][u] + w;
                    pq.push(lli(d[mask][v], v) );
                }
            }
        }
    }

    long long ans = inf;
    for (int u = 1; u <= n; ++u) ans = min(ans, d[(1 << K) - 1][u]);
    printf("%lld", ans);

    return 0;
}

Compilation message

cities.cpp: In function 'int main()':
cities.cpp:24:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d", &n, &K, &m);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
cities.cpp:27:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int u; scanf("%d", &u);
                ~~~~~^~~~~~~~~~
cities.cpp:33:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int u, v, w; scanf("%d %d %d", &u, &v, &w);
                      ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 27640 KB Output is correct
2 Correct 22 ms 27768 KB Output is correct
3 Correct 23 ms 27936 KB Output is correct
4 Correct 23 ms 27936 KB Output is correct
5 Correct 23 ms 27936 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 788 ms 45004 KB Output is correct
2 Correct 644 ms 49204 KB Output is correct
3 Correct 547 ms 49204 KB Output is correct
4 Correct 106 ms 49204 KB Output is correct
5 Correct 442 ms 59140 KB Output is correct
6 Correct 100 ms 59140 KB Output is correct
7 Correct 25 ms 59140 KB Output is correct
8 Correct 25 ms 59140 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 59140 KB Output is correct
2 Correct 29 ms 59140 KB Output is correct
3 Correct 26 ms 59140 KB Output is correct
4 Correct 26 ms 59140 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1477 ms 67192 KB Output is correct
2 Correct 1465 ms 71376 KB Output is correct
3 Correct 1083 ms 71376 KB Output is correct
4 Correct 680 ms 74428 KB Output is correct
5 Correct 222 ms 75160 KB Output is correct
6 Correct 106 ms 78540 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2450 ms 89276 KB Output is correct
2 Correct 2435 ms 93516 KB Output is correct
3 Correct 2784 ms 97756 KB Output is correct
4 Correct 1710 ms 97756 KB Output is correct
5 Correct 1387 ms 100784 KB Output is correct
6 Correct 300 ms 101544 KB Output is correct
7 Correct 120 ms 104820 KB Output is correct