oj.uz

Submission #632972

# Submission time Handle Problem Language Result Execution time Memory
632972 2022-08-21T10:30:26 Z lto5 Cities (BOI16_cities) C++17
0 / 100
 21 ms 5588 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 >> m >> k;
  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
0 / 22.0

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

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 14 ms 5540 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 21 ms 5588 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 16 ms 5588 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Runtime error 15 ms 5540 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -