Submission #375759

#	Time	Username	Problem	Language	Result	Execution time	Memory
375759		rama_pang	Robot (JOI21_ho_t4)	C++14	100 / 100	1274 ms	88848 KiB

Main

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

using lint = long long;

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);

  int N, M;
  cin >> N >> M;

  vector<map<int, lint>> S(N);
  vector<map<int, vector<pair<int, int>>>> adj(N);
  for (int i = 0; i < M; i++) {
    int u, v, c, w;
    cin >> u >> v >> c >> w;
    u--, v--;
    S[u][c] += w;
    S[v][c] += w;
    adj[u][c].push_back({v, w});
    adj[v][c].push_back({u, w});
  }

  // Options when traversing an edge:
  // - Change the next road
  //   - Costs P[e]
  // - Change other adjacent road, last road unchanged or has different color
  //   - Costs S[u][C[e]] - P[e]
  // - Change other adjacent road, last road changed and has same color
  //   - Costs S[u][C[e]] - P[e] - P[last]
  //
  // dist[u][0] = minimum cost to vertex u, no restrictions
  // dist[u][c] = minimum cost to vertex u, where the next road must be of color c (use option 3 next)

  vector<map<int, lint>> dist(N);
  priority_queue<array<lint, 3>, vector<array<lint, 3>>, greater<array<lint, 3>>> pq;

  const auto Relax = [&](int u, int c, lint d) {
    if (dist[u].count(c) == 0 || dist[u][c] > d) {
      dist[u][c] = d;
      pq.push({d, u, c});
    }
  };

  Relax(0, 0, 0);
  while (!pq.empty()) {
    lint d = pq.top()[0];
    int u = (int) pq.top()[1];
    int c = (int) pq.top()[2];
    pq.pop();
    if (dist[u][c] != d) {
      continue;
    }
    if (c == 0) {
      for (const auto &adjc : adj[u]) {
        for (const auto &[v, w] : adjc.second) {
          Relax(v, 0, d + w); // Option 1
          Relax(v, 0, d + S[u][adjc.first] - w); // Option 2
          Relax(v, adjc.first, d); // Option 3, Part 1
        }
      }
    } else {
      for (const auto &[v, w] : adj[u][c]) {
        Relax(v, 0, d + S[u][c] - w); // Option 3, Part 2
      }
    }
  }

  cout << (dist[N - 1].count(0) ? dist[N - 1][0] : -1) << '\n';
  return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:57:26: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   57 |         for (const auto &[v, w] : adjc.second) {
      |                          ^
Main.cpp:64:24: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   64 |       for (const auto &[v, w] : adj[u][c]) {
      |                        ^

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