oj.uz

답안 #258310

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
258310 2020-08-05T17:17:09 Z rama_pang Cities (BOI16_cities) C++14
100 / 100
 2616 ms 73956 KB 
#include <bits/stdc++.h>
using namespace std;

using lint = long long;

struct State {
  int u, mask;
  lint d;
  State() {}
  State(int u, int mask, lint d) : u(u), mask(mask), d(d) {}
  bool operator < (const State &o) const {
    return d > o.d || (d == o.d && mask > o.mask); // for pq
  }
};

lint dist[100005][1 << 4];
vector<pair<int, int>> radj[100005];
priority_queue<State> pq;

lint Solve(int N, int K, int M, vector<int> special, vector<vector<pair<int, int>>> adj) {
  for (int i = 0; i < N; i++) {
    for (auto j : adj[i]) if (j.first != -1) {
      radj[j.first].emplace_back(i, j.second);
    }
  }

  for (int i = 0; i < N; i++) {
    for (int j = 0; j < (1 << (K - 1)); j++) {
      dist[i][j] = 1e18;
    }
  }

  auto Relax = [&](int u, int mask, lint d) {
    if (dist[u][mask] > d) {
      dist[u][mask] = d;
      pq.emplace(u, mask, d);
    }
  };
  vector<int> specialid(N, -1);
  for (int i = 0; i < (K - 1); i++) {
    specialid[special[i]] = i;
    Relax(i, 0, 0);
  }
  for (int i = 0; i < N; i++) {
    Relax(i, 0, 0);
  }
  while (!pq.empty()) {
    State s = pq.top();
    pq.pop();
    if (dist[s.u][s.mask] != s.d) {
      continue;
    }
    if (specialid[s.u] != -1) {
      Relax(s.u, s.mask | (1 << specialid[s.u]), dist[s.u][s.mask]);
    }
    int othermask = ((1 << (K - 1)) - 1) ^ s.mask;
    for (int m = othermask; m > 0; m = (m - 1) & othermask) {
      Relax(s.u, s.mask | m, dist[s.u][s.mask] + dist[s.u][m]);
    }      
    for (auto v : radj[s.u]) {
      Relax(v.first, s.mask, s.d + v.second);
    }
  }
  return dist[special.back()][(1 << (K - 1)) - 1];
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);

  int N, K, M;
  cin >> N >> K >> M;

  vector<int> special(K);
  for (int i = 0; i < K; i++) {
    cin >> special[i];
    special[i]--;
  }

  vector<vector<pair<int, int>>> edgelist(N);
  for (int i = 0; i < M; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    u--, v--;
    edgelist[u].emplace_back(v, w);
    edgelist[v].emplace_back(u, w);
  }

  cout << Solve(N, K, M, special, edgelist) << "\n";
  return 0;
}

Subtask #1
22.0 / 22.0

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

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 462 ms 45196 KB Output is correct
2 Correct 429 ms 44528 KB Output is correct
3 Correct 231 ms 34032 KB Output is correct
4 Correct 84 ms 18552 KB Output is correct
5 Correct 300 ms 43248 KB Output is correct
6 Correct 82 ms 18296 KB Output is correct
7 Correct 4 ms 3072 KB Output is correct
8 Correct 4 ms 3072 KB Output is correct

Subtask #3
15.0 / 15.0

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

Subtask #4
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1123 ms 57556 KB Output is correct
2 Correct 997 ms 56904 KB Output is correct
3 Correct 567 ms 40164 KB Output is correct
4 Correct 661 ms 38756 KB Output is correct
5 Correct 189 ms 25040 KB Output is correct
6 Correct 84 ms 22152 KB Output is correct

Subtask #5
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2616 ms 73956 KB Output is correct
2 Correct 2593 ms 73920 KB Output is correct
3 Correct 2348 ms 73668 KB Output is correct
4 Correct 1530 ms 48400 KB Output is correct
5 Correct 1523 ms 63300 KB Output is correct
6 Correct 265 ms 29024 KB Output is correct
7 Correct 98 ms 22524 KB Output is correct