oj.uz

답안 #204836

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
204836 2020-02-27T10:42:36 Z nickyrio Cities (BOI16_cities) C++17
100 / 100
 2486 ms 42468 KB 
#include <bits/stdc++.h>

using namespace std;
#define long long long
#define pp pair<long, 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 = 2e16;

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; ++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';
}

Subtask #1
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 2680 KB Output is correct
2 Correct 6 ms 2680 KB Output is correct
3 Correct 6 ms 2680 KB Output is correct
4 Correct 6 ms 2808 KB Output is correct
5 Correct 6 ms 2808 KB Output is correct

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 821 ms 23528 KB Output is correct
2 Correct 791 ms 22624 KB Output is correct
3 Correct 440 ms 16492 KB Output is correct
4 Correct 288 ms 11900 KB Output is correct
5 Correct 564 ms 20324 KB Output is correct
6 Correct 266 ms 11640 KB Output is correct
7 Correct 12 ms 2936 KB Output is correct
8 Correct 9 ms 2808 KB Output is correct

Subtask #3
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 3064 KB Output is correct
2 Correct 13 ms 3064 KB Output is correct
3 Correct 10 ms 2936 KB Output is correct
4 Correct 12 ms 2936 KB Output is correct

Subtask #4
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1380 ms 29796 KB Output is correct
2 Correct 1305 ms 28888 KB Output is correct
3 Correct 829 ms 22632 KB Output is correct
4 Correct 869 ms 21612 KB Output is correct
5 Correct 392 ms 13660 KB Output is correct
6 Correct 302 ms 14064 KB Output is correct

Subtask #5
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2486 ms 42468 KB Output is correct
2 Correct 2462 ms 42340 KB Output is correct
3 Correct 2390 ms 41544 KB Output is correct
4 Correct 1585 ms 35208 KB Output is correct
5 Correct 1380 ms 27924 KB Output is correct
6 Correct 485 ms 15044 KB Output is correct
7 Correct 292 ms 14200 KB Output is correct