Download Speed

input/code.cpp: In function 'int main()':
input/code.cpp:69:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |     for (int ii = 0; ii < (path.size() - 1); ii++) {
      |                      ~~~^~~~~~~~~~~~~~~~~~~

#include <bits/stdc++.h>
#include <vector>
#define ll long long

template <typename T>
std::ostream &operator<<(std::ostream &os, const std::vector<T> &v) {
  os << "[";
  for (int i = 0; i < v.size(); ++i) {
    os << v[i];
    if (i != v.size() - 1)
      os << ", ";
  }
  os << "]";
  return os;
}

ll something(std::vector<std::unordered_map<ll, ll>> &costMap,
             std::vector<std::unordered_map<ll, ll>> &emptMap,
             std::vector<char> &checked, std::vector<ll> &path, ll start,
             ll wholeEnd) {
  path.push_back(start);
  if (start == wholeEnd) {
    return 1e15;
  }
  checked[start] = 1;

  for (const auto &[end, speed] : costMap[start]) {
    if (speed > 0 && !checked[end]) {
      ll ret = something(costMap, emptMap, checked, path, end, wholeEnd);
      if (ret != -1) {
        return std::min(ret, costMap[start][end]);
      }
    }
  }
  path.pop_back();
  return -1;
}

int main() {
  ll compCount, conCount;
  std::cin >> compCount;
  std::cin >> conCount;

  //   std::cout << compCount << " " << conCount << std::endl;
  std::vector<std::unordered_map<ll, ll>> costMap(compCount,
                                                  std::unordered_map<ll, ll>());
  std::vector<std::unordered_map<ll, ll>> emptMap(compCount,
                                                  std::unordered_map<ll, ll>());
  for (ll ii = 0; ii < conCount; ii++) {
    ll start, end, speed;
    // std::cout << start << " " << end << " " << speed << std::endl;
    std::cin >> start;
    std::cin >> end;
    std::cin >> speed;
    costMap[start - 1][end - 1] = speed;
    costMap[end - 1][start - 1] = 0;
  }
  std::vector<char> checked(compCount, 0);
  ll minCost = 0;
  ll throughtPut = 0;
  while (1) {
    std::vector<ll> path;
    minCost = something(costMap, emptMap, checked, path, 0, compCount - 1);
    if (minCost == -1)
      break;

    throughtPut += minCost;
    // std::cout << path << " " << minCost << std::endl;
    for (int ii = 0; ii < (path.size() - 1); ii++) {
      ll start = path[ii];
      ll end = path[ii + 1];
      costMap[start][end] -= minCost;
      costMap[end][start] += minCost;
    }
  };
  std::cout << throughtPut << std::endl;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: WRONG ANSWER

Test 6

Verdict: WRONG ANSWER

Test 7

Verdict: WRONG ANSWER

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: WRONG ANSWER

Test 11

Verdict: WRONG ANSWER

Test 12

Verdict: ACCEPTED