Submission #1273752

#	Time	Username	Problem	Language	Result	Execution time	Memory
1273752		marcus06	Robot (JOI21_ho_t4)	C++20	100 / 100	870 ms	83560 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/CP/Library/debug.h>
#else
#define debug(...) 
#endif

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

void solve() {
  int N, M;
  cin >> N >> M;
  vector <map <int, vector <pair <int, int>>>> graph(N);
  vector <map <int, lli>> cost(N);
  for (int i = 0; i < M; ++i) {
    int u, v, c, p;
    cin >> u >> v >> c >> p;
    --u, --v;
    cost[u][c] += p;
    cost[v][c] += p;
    graph[u][c].emplace_back(v, p);
    graph[v][c].emplace_back(u, p);
  }

  vector <map <int, lli>> dist(N);
  priority_queue <array <lli, 3>> Q;
  dist[0][0] = 0;
  Q.push({0, 0, 0});

  while (!Q.empty()) {
    auto [d, u, c] = Q.top(); Q.pop();
    d = -d;
    if (d > dist[u][c]) continue;

    if (c != 0) {
      for (auto [v, p]: graph[u][c]) {
        lli w = cost[u][c] - p;
        if (dist[v].find(0) == dist[v].end() || dist[v][0] > d + w) {
          dist[v][0] = d + w;
          Q.push({-dist[v][0], v, 0});
        }
      }
    } else {
      for (auto [nxt_c, arr]: graph[u]) {
        for (auto [v, p]: arr) {
          if (dist[v].find(0) == dist[v].end() || dist[v][0] > d + p) {
            dist[v][0] = d + p;
            Q.push({-dist[v][0], v, 0});
          }

          if (dist[v].find(0) == dist[v].end() || dist[v][0] > d + cost[u][nxt_c] - p) {
            dist[v][0] = d + cost[u][nxt_c] - p;
            Q.push({-dist[v][0], v, 0});
          }

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

  lli ans = -1;
  if (dist[N - 1].find(0) != dist[N - 1].end()) ans = dist[N - 1][0];
  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: 34 / 34
• Subtask 2: 24 / 24
• Subtask 3: 42 / 42