Submission #22952

#	Time	Username	Problem	Language	Result	Execution time	Memory
22952		Bruteforceman	Cities (BOI16_cities)	C++11	100 / 100	3333 ms	43964 KiB

cities

#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 (stderr)

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 / 22
• Subtask 2: 14 / 14
• Subtask 3: 15 / 15
• Subtask 4: 23 / 23
• Subtask 5: 26 / 26