Submission #286983

#	Time	Username	Problem	Language	Result	Execution time	Memory
286983		AlexLuchianov	Cities (BOI16_cities)	C++14	36 / 100	2532 ms	44184 KiB

cities

#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 & (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 (stderr)

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