제출 #632974

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
632974		lto5	Cities (BOI16_cities)	C++14	100 / 100	1923 ms	43576 KiB

cities

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