oj.uz

Submission #286986

# Submission time Handle Problem Language Result Execution time Memory
286986 2020-08-31T08:28:31 Z AlexLuchianov Cities (BOI16_cities) C++14
100 / 100
 2655 ms 44232 KB 
#include <iostream>
#include <vector>
#include <cassert>
#include <cmath>
#include <queue>

using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))

ll const inf = 1000000000000000000;
int const nmax = 100000;
int const sigma = 5;

ll dp[1 << sigma][1 + nmax];
int special[1 + nmax];
std::vector<std::pair<int,int>> g[1 + nmax];

void solvelayer(int mask, int n) {
  std::priority_queue<std::pair<ll,int>, std::vector<std::pair<ll,int>>, std::greater<std::pair<ll,int>>> pq;
  for(int mask2 = mask; 0 < mask2; mask2 = (mask2 - 1) & mask)
    for(int i = 1; i <= n; i++)
      dp[mask][i] = std::min(dp[mask][i], dp[mask2][i] + dp[mask2 ^ mask][i]);
  for(int i = 1; i <= n; i++)
    pq.push({dp[mask][i], i});
  
  while(0 < pq.size()) {
    int node = pq.top().second;
    ll cost = pq.top().first;
    pq.pop();
    if(dp[mask][node] != cost)
      continue;

    for(int h = 0; h < g[node].size();h ++) {
      int to = g[node][h].first;
      if(cost + g[node][h].second < dp[mask][to]) {
        dp[mask][to] = cost + g[node][h].second;
        pq.push({dp[mask][to], to});
      }
    }
  }
}

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

  int n, k, m;
  std::cin >> n >> k >> m;
  for(int i = 1; i < (1 << sigma); i++)
    for(int j = 1; j <= n; j++)
      dp[i][j] = inf;
  
  for(int i = 1;i <= k; i++) {
    int val;
    std::cin >> val;
    special[val] = i;
    dp[(1 << (i - 1))][val] = 0;
  }
  
  for(int i = 1;i <= m; i++) {
    int x, y, cost;
    std::cin >> x >> y >> cost;
    g[x].push_back({y, cost});
    g[y].push_back({x, cost});
  }

  for(int mask = 0; mask < (1 << k); mask++) {
    solvelayer(mask, n);
  }
  ll result = inf;
  for(int i = 1; i <= n; i++)
    result = std::min(result, dp[(1 << k) - 1][i]);
  std::cout << result;
  return 0;
}

Compilation message

cities.cpp: In function 'void solvelayer(int, int)':
cities.cpp:34:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |     for(int h = 0; h < g[node].size();h ++) {
      |                    ~~^~~~~~~~~~~~~~~~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2816 KB Output is correct
2 Correct 2 ms 2816 KB Output is correct
3 Correct 2 ms 2816 KB Output is correct
4 Correct 2 ms 2816 KB Output is correct
5 Correct 2 ms 2816 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 708 ms 39848 KB Output is correct
2 Correct 719 ms 39836 KB Output is correct
3 Correct 475 ms 33864 KB Output is correct
4 Correct 82 ms 7876 KB Output is correct
5 Correct 387 ms 39724 KB Output is correct
6 Correct 73 ms 7712 KB Output is correct
7 Correct 6 ms 3200 KB Output is correct
8 Correct 5 ms 3200 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 3200 KB Output is correct
2 Correct 8 ms 3200 KB Output is correct
3 Correct 7 ms 3200 KB Output is correct
4 Correct 6 ms 3072 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1307 ms 39948 KB Output is correct
2 Correct 1313 ms 40136 KB Output is correct
3 Correct 837 ms 33772 KB Output is correct
4 Correct 702 ms 28652 KB Output is correct
5 Correct 181 ms 15532 KB Output is correct
6 Correct 81 ms 12792 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2603 ms 39776 KB Output is correct
2 Correct 2655 ms 39916 KB Output is correct
3 Correct 2513 ms 44232 KB Output is correct
4 Correct 1746 ms 36004 KB Output is correct
5 Correct 1259 ms 28632 KB Output is correct
6 Correct 275 ms 15556 KB Output is correct
7 Correct 97 ms 12784 KB Output is correct