Submission #491813

#	Time	Username	Problem	Language	Result	Execution time	Memory
491813		mickytanawin	Robot (JOI21_ho_t4)	C++17	100 / 100	816 ms	83092 KiB

Main

#include <cstddef>
#include <cstdint>
#include <iostream>
#include <limits>
#include <map>
#include <queue>
#include <utility>
#include <vector>

int main() {
  using usize = std::size_t;
  using u64 = std::uint64_t;
  struct edge_type {
    usize to;
    u64 cost;

    bool operator<(const edge_type &r) const { return cost > r.cost; }
  };

  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);

  usize N, M;
  std::cin >> N >> M;

  const usize ext_N = N + 2 * M;

  std::vector<std::vector<edge_type>> graph(ext_N);

  {
    usize next_id = N;
    std::map<std::pair<usize, usize>, usize> id_map;

    const auto id = [&](const usize v, const usize c) -> usize {
      const auto [itr, success] = id_map.insert({{v, c}, next_id});
      if (success) {
        next_id += 1;
      }
      return itr->second;
    };

    std::vector<u64> sum(ext_N, 0);

    for (usize i = 0; i != M; i += 1) {
      usize A, B, C;
      u64 P;
      std::cin >> A >> B >> C >> P;
      A -= 1;
      B -= 1;
      for (usize t = 0; t != 2; t += 1) {
        std::swap(A, B);

        sum[id(A, C)] += P;
        graph[A].push_back({B, P});
        graph[A].push_back({id(B, C), 0});

        graph[id(A, C)].push_back({B, -P});
      }
    }

    for (const auto &[key, u] : id_map) {
      const auto &[v, c] = key;
      graph[v].push_back({u, 0});
      for (edge_type &edge : graph[u]) {
        edge.cost += sum[u];
      }
    }
  }

  static constexpr u64 Inf = std::numeric_limits<u64>::max();
  std::vector<u64> dist(ext_N, Inf);
  {
    std::priority_queue<edge_type> que;
    const auto push = [&](const usize v, const u64 d) -> void {
      if (dist[v] > d) {
        dist[v] = d;
        que.push({v, d});
      }
    };
    push(0, 0);
    while (!que.empty()) {
      const usize v = que.top().to;
      const u64 d = que.top().cost;
      que.pop();
      if (dist[v] < d) {
        continue;
      }
      for (const edge_type &edge : graph[v]) {
        push(edge.to, d + edge.cost);
      }
    }
  }

  if (dist[N - 1] == Inf) {
    std::cout << "-1\n";
  } else {
    std::cout << dist[N - 1] << "\n";
  }

  return 0;
}

• Subtask 1: 34 / 34
• Subtask 2: 24 / 24
• Subtask 3: 42 / 42