oj.uz

Submission #22952

# Submission time Handle Problem Language Result Execution time Memory
22952 2017-04-30T17:11:48 Z Bruteforceman Cities (BOI16_cities) C++11
100 / 100
 3333 ms 43964 KB 
#include <bits/stdc++.h>
using namespace std;
typedef pair <int, int> pii;
long long d[1 << 5][100010];
vector <pii> g[100010];
int imp[10];
const long long inf = 1e16;
bool v[100010];

struct data {
    int node;
    long long cost;
    data (int node, long long cost) : node(node), cost(cost) {}
    data () {}
    bool operator < (const data x) const {
        return cost > x.cost;
    }
};

int main() {
    int n, k, m;
    scanf("%d %d %d", &n, &k, &m);
    for(int i = 1; i <= k; i++) {
        scanf("%d", &imp[i]);
    } 
    for(int i = 1; i <= m; i++) {
        int p, q, r;
        scanf("%d %d %d", &p, &q, &r);
        g[p].push_back(pii(q, r));
        g[q].push_back(pii(p, r));
    }
    for(int i = 1; i < (1 << k); i++) {
        for(int j = 1; j <= n; j++) {
            d[i][j] = inf;
        }
    }
    for(int i = 0; i < k; i++) {
        d[1 << i][imp[i + 1]] = 0;
    }
    for(int x = 1; x < (1 << k); x++) {
        for(int y = 0; y < x; y++) {
            if((x | y) == x) {
                for(int z = 1; z <= n; z++) {
                    d[x][z] = min(d[y][z] + d[x ^ y][z], d[x][z]);
                }
            }
        }
        priority_queue <data> Q;
        for(int i = 1; i <= n; i++) {
            if(d[x][i] < inf) {
                Q.emplace(i, d[x][i]);
            }
        }
        fill(v + 1, v + n + 1, false);
        while(not Q.empty()) {
            int node = Q.top().node;
            long long cost = Q.top().cost;
            Q.pop();
            if(v[node] == true) continue;
            v[node] = true;
            for(auto i : g[node]) {
                int p = i.first;
                int r = i.second;
                if(d[x][p] > cost + r) {
                    d[x][p] = cost + r;
                    Q.emplace(p, cost + r);
                }
            }
        }
    }
    long long ans = inf;
    for(int i = 1; i <= n; i++) {
        ans = min(ans, d[(1 << k) - 1][i]);
    }
    printf("%lld\n", ans);
    return 0;
}

Compilation message

cities.cpp: In function 'int main()':
cities.cpp:22:34: 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:24:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &imp[i]);
                             ^
cities.cpp:28:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d", &p, &q, &r);
                                      ^

Subtask #1
22.0 / 22.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 809 ms 43964 KB Output is correct
2 Correct 736 ms 43896 KB Output is correct
3 Correct 423 ms 36764 KB Output is correct
4 Correct 106 ms 34136 KB Output is correct
5 Correct 399 ms 41916 KB Output is correct
6 Correct 86 ms 34156 KB Output is correct
7 Correct 3 ms 29600 KB Output is correct
8 Correct 3 ms 29600 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 29600 KB Output is correct
2 Correct 3 ms 29600 KB Output is correct
3 Correct 3 ms 29608 KB Output is correct
4 Correct 3 ms 29600 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1509 ms 43956 KB Output is correct
2 Correct 1543 ms 43752 KB Output is correct
3 Correct 879 ms 36768 KB Output is correct
4 Correct 729 ms 39372 KB Output is correct
5 Correct 223 ms 35744 KB Output is correct
6 Correct 116 ms 35760 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2833 ms 43960 KB Output is correct
2 Correct 3083 ms 43952 KB Output is correct
3 Correct 3333 ms 43800 KB Output is correct
4 Correct 1889 ms 36768 KB Output is correct
5 Correct 1503 ms 39372 KB Output is correct
6 Correct 353 ms 35728 KB Output is correct
7 Correct 106 ms 35624 KB Output is correct