oj.uz

Submission #204828

# Submission time Handle Problem Language Result Execution time Memory
204828 2020-02-27T10:21:35 Z nickyrio Cities (BOI16_cities) C++17
0 / 100
 607 ms 42544 KB 
#include <bits/stdc++.h>

using namespace std;
#define long long long
#define pp pair<int, long>

const int N = 1e5 + 100;
const int K = 5;

long d[1 << K][N];
vector<pp> e[N];
int star[N];

void Min(long &a, long b){ a = (a > b ? b : a); }
const long inf = 2e18;

int main() {
    int n, k, m;
    cin >> n >> k >> m;
    priority_queue<pp> q;
    for (int i = 0; i < (1 << k); ++i) for (int j = 0; j < n; ++j) d[i][j] = inf;
    for (int i = 0; i < k; ++i) {
        int x; cin >> x;
        --x;
        d[1 << i][x] = 0;
    }
    for (int i = 0; i < m; ++i) {
        int u, v, c;
        cin >> u >> v >> c;
        --u, --v;
        e[u].push_back(pp(v, c));
        e[v].push_back(pp(u, c));
    }
    for (int mask = 0; mask < (1 << k); ++mask) {
        for (int preMask = 0; preMask < mask / 2; ++preMask) if (mask & preMask == preMask) {
            int sufMask = mask ^ preMask;
            //if (sufMask > preMask) continue;
            for (int i = 0; i < n; ++i) {
                Min(d[mask][i], d[preMask][i] + d[sufMask][i]);
            }
        }
        for (int i = 0; i < n; ++i) if (d[mask][i] != inf) q.emplace(-d[mask][i], i);
        while (!q.empty()) {
            int u = q.top().second;
            long dist = -q.top().first;
            q.pop();
            if (d[mask][u] != dist) continue;
         //   cerr << "Say " << mask << ' ' << u << ' ' << dist << '\n';
            for (auto t : e[u]) {
                int v = t.first;
                long c = t.second;
                if (d[mask][v] > d[mask][u] + c) {
                    d[mask][v] = d[mask][u] + c;
                    q.emplace(-d[mask][v], v);
             //       cerr << "To " << v << ' ' << d[mask][v] << '\n';
                }
            }
        }
    }
    long ans = *min_element(d[(1 << k) - 1], d[(1 << k) - 1] + n);
    cout << ans << '\n';
}

Compilation message

cities.cpp: In function 'int main()':
cities.cpp:35:81: warning: self-comparison always evaluates to true [-Wtautological-compare]
         for (int preMask = 0; preMask < mask / 2; ++preMask) if (mask & preMask == preMask) {
                                                                         ~~~~~~~~^~~~~~~~~~
cities.cpp:35:81: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]

Subtask #1
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 2680 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 399 ms 23672 KB Output is correct
2 Correct 607 ms 24828 KB Output is correct
3 Incorrect 197 ms 16248 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 3064 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 424 ms 29920 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 445 ms 42544 KB Output isn't correct
2 Halted 0 ms 0 KB -