Submission #1270767

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270767		marcus06	Robot (JOI21_ho_t4)	C++20	0 / 100	3096 ms	104196 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using lli = long long;

/*How to use:
  Tvector <int, 2> g(n); //graph
  Tvector <int, 3> f(n, k, 2) = f[n][k][2]
*/
template <class Tp, int D = 1>
struct Tvector : public vector<Tvector<Tp, D - 1>> {
  template <class... Args>
  Tvector(int n = 0, Args... args) : vector<Tvector<Tp, D - 1>>(n, Tvector<Tp, D - 1>(args...)) {}
};

template <class Tp>
struct Tvector<Tp, 1> : public vector<Tp> {
  Tvector(int n = 0, Tp val = Tp()) : vector<Tp>(n, val) {}
};

#ifdef LOCAL
#include </home/marcus06/mycp/Library/debug.h>
#else
#define debug(...) 
#endif

const int INF = int(1e9) + 7;

void solve() {
  int N, M;
  cin >> N >> M;
  Tvector <array <int, 3>, 2> graph(N);
  vector <map <int, int>> cost(N);
  vector <map <int, pair <int, int>>> edge_info(N);
  for (int i = 0; i < M; ++i) {
    int A, B, C, P;
    cin >> A >> B >> C >> P;
    --A, --B;
    cost[A][C] += P;
    cost[B][C] += P;
    edge_info[A][B] = edge_info[B][A] = {C, P};
    graph[A].push_back({B, C, P});
    graph[B].push_back({A, C, P});
  }

  vector <map <pair <int, int>, lli>> dist(N);
  priority_queue <array <lli, 4>> Q;

  Q.push({0, 0, INF, 0});
  dist[0][{INF, 0}] = 0;
  while (!Q.empty()) {
    auto [d, u, color, parent] = Q.top(); Q.pop();
    d = -d;
    if (d > dist[u][{color, parent}]) continue;

    for (auto [v, nxt_color, price]: graph[u]) {
      if (dist[v].find({INF, u}) == dist[v].end() || dist[v][{INF, u}] > d + price) {
        dist[v][{INF, u}] = d + price;
        Q.push({-dist[v][{INF, u}], v, INF, u});
      }

      int w = cost[u][nxt_color] - price;
      if (color == INF) {
        auto [C, P] = edge_info[u][parent];
        if (nxt_color == C) w -= P;
      }
      if (w < 0) continue;

      if (dist[v].find({nxt_color, u}) == dist[v].end() || dist[v][{nxt_color, u}] > d + w) {
        dist[v][{nxt_color, u}] = d + w;
        Q.push({-dist[v][{nxt_color, u}], v, nxt_color, u});
      }
    }
  }

  lli ans = lli(1e18) + 7;
  for (auto itr: dist[N - 1]) {
    ans = min(ans, itr.second);
  }
  if (dist[N - 1].empty()) ans = -1;
  cout << ans << '\n';
}

int main() {
  std::cin.tie(0)->sync_with_stdio(0);
#ifdef LOCAL
  auto begin = std::chrono::high_resolution_clock::now();
#endif

  int tt = 1;
  while (tt--) {
    solve();
  }

#ifdef LOCAL
  auto end = std::chrono::high_resolution_clock::now();
  auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
  std::cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n";
#endif
  return 0;
}

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