oj.uz

답안 #632974

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
632974 2022-08-21T10:30:59 Z lto5 Cities (BOI16_cities) C++14
100 / 100
 1923 ms 43576 KB 
#include<bits/stdc++.h>
using namespace std;

const int MAX_N = 1e5 + 5,
          MAX_K = 10;
const long long INF = 4557430888798830399;

struct Node{
  int u, mask;
  long long w;

  Node(int _u = 0, int _m = 0, long long _w = 0){
    u = _u,
    mask = _m,
    w = _w;
  }

  bool operator < (const Node &c) const {
    return w > c.w;
  }
};


int n, k, m;
int idSpec[MAX_N];
long long f[1 << MAX_K][MAX_N];
vector<pair<int, int>> g[MAX_N];
vector<int> subMask[1 << MAX_K];

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

  memset(idSpec, -1, sizeof(idSpec));

  cin >> n >> k >> m;
  for(int i = 0, x; i < k; i++){
    cin >> x;
    idSpec[x] = i;
  }
  for(int i = 1, u, v, w; i <= m; i++){
    cin >> u >> v >> w;
    g[u].push_back({v, w});
    g[v].push_back({u, w});
  }

  for(int mask = 0; mask <= 1 << k; mask++)
    for(int u = 1; u <= n; u++)
      f[mask][u] = INF;
//  memset(f, 0x3f, sizeof(f));

  for(int u = 1; u <= n; u++)
    if(idSpec[u] != -1)
      f[1 << idSpec[u]][u] = 0;

  priority_queue<Node> pq;

  for(int mask = 0; mask < 1 << k; mask++){
    for(int prv = 0; prv < mask; prv++){
      if((mask & prv) == 0)
        continue;

      int rem = mask ^ prv;
      for(int u = 1; u <= n; u++){
        f[mask][u] = min(f[mask][u], f[prv][u] + f[rem][u]);
      }
    }

    for(int u = 1; u <= n; u++)
      if(f[mask][u] != INF){
        pq.push(Node(u, mask, f[mask][u]));
      }
    while(!pq.empty()){
      Node cur = pq.top();
      pq.pop();

      int u = cur.u,
          msk = cur.mask;
      long long du = cur.w;

      if(f[msk][u] != du)
        continue;

      for(auto x: g[u]){
        int v = x.first,
            w = x.second;
        int nxt = msk;
        if(f[nxt][v] > du + w)
          f[nxt][v] = du + w,
          pq.push(Node(v, nxt, f[nxt][v]));
      }
    }

  }
  long long ans = INF;
  for(int u = 1; u <= n; u++)
    ans = min(ans, f[(1 << k) - 1][u]);

  cout << ans;
  return 0;
}

Subtask #1
22.0 / 22.0

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

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 489 ms 24796 KB Output is correct
2 Correct 441 ms 24320 KB Output is correct
3 Correct 261 ms 17472 KB Output is correct
4 Correct 69 ms 11244 KB Output is correct
5 Correct 246 ms 21696 KB Output is correct
6 Correct 53 ms 11232 KB Output is correct
7 Correct 3 ms 3284 KB Output is correct
8 Correct 3 ms 3236 KB Output is correct

Subtask #3
15.0 / 15.0

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

Subtask #4
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 919 ms 31032 KB Output is correct
2 Correct 843 ms 30764 KB Output is correct
3 Correct 553 ms 23832 KB Output is correct
4 Correct 502 ms 21952 KB Output is correct
5 Correct 143 ms 13616 KB Output is correct
6 Correct 63 ms 13004 KB Output is correct

Subtask #5
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1811 ms 43472 KB Output is correct
2 Correct 1923 ms 43576 KB Output is correct
3 Correct 1837 ms 43276 KB Output is correct
4 Correct 1104 ms 36336 KB Output is correct
5 Correct 872 ms 28212 KB Output is correct
6 Correct 197 ms 14920 KB Output is correct
7 Correct 68 ms 13332 KB Output is correct