Участник:Nik7/Ada and Cities

Материал из DISCOPAL
Перейти к: навигация, поиск

«Ada and Cities»

// C++14 (gcc 8.3)
 
#include <iostream>
#include <vector>
#include <algorithm>
 
constexpr auto N_MAX = 501lu;
constexpr auto F_MAX = 501lu;
constexpr auto M_MAX = 10001lu;
constexpr auto T_MAX = 500000001lu;
 
int roads[N_MAX][N_MAX];
int friend_city[N_MAX];
 
std::vector<int> road[N_MAX];
std::vector<int> matches;
std::vector<int> reachable;
 
int search_cities(int f) {
  if (reachable[f]) {
    return 0;
  }
  reachable[f] = 1;
  for (int i = 0; i < road[f].size(); i++) {
    int r = road[f][i];
    if(matches[r] == -1 || search_cities(matches[r])){
      matches[r] = f;
      return 1;
    }
  }
  return 0;
}
 
void process_case() {
  int N, F, M, T;
  std::cin >> N >> M >> F >> T;
  for (auto i = 1; i <= N; ++i) {
    for (auto j = 1; j <= N; ++j) {
      roads[i][j] = T_MAX;
    }
    roads[i][i] = 0;
  }
  for (auto i = 1; i <= F; ++i) {
    road[i].clear();
    std::cin >> friend_city[i];
  }
  for (int i = 1; i <= M; ++i) {
    int A, B, L;
    std::cin >> A >> B >> L;
    roads[A][B] = std::min(roads[A][B], L);
    roads[B][A] = std::min(roads[B][A], L);
  }
  for (int k = 1; k <= N; ++k) {
    for (int j = 1; j <= N; ++j) {
      for (int i = 1; i <= N; ++i) {
        roads[i][j] = std::min(roads[i][j], roads[i][k] + roads[k][j]);
      }
    }
  }
  for (int i = 1; i <= F; ++i) {
    for (int j = 1; j <= N; ++j) {
      if (roads[friend_city[i]][j] <= T) {
        road[i].push_back(j);
      }
    }
  }
  auto res = 0;
  matches.assign(N + 2, -1);
  for (auto i = 1; i <= F; ++i) {
    reachable.assign(F+1, 0);
    res += search_cities(i);
  }
  std::cout << res << std::endl;
}
 
int main() {
  int num_cases;
  std::cin >> num_cases;
  for (auto case_num = 0; case_num < num_cases; ++case_num) {
    process_case();
  }
  return 0;
}