Submission #1296374

#	Time	Username	Problem	Language	Result	Execution time	Memory
1296374		alan_c	Robot (JOI21_ho_t4)	C++20	100 / 100	1063 ms	81496 KiB

Main

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

using ll = long long;

const int N = 1e5+1;
map<int, vector<pair<int, int>>> adj[N];
map<int, ll> ctotal[N], cost[N]; // cost[i][0] is no color change to i

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

  int n, m; cin >> n >> m;
  while (m--) {
    int a, b, c, p; cin >> a >> b >> c >> p;
    adj[a][c].emplace_back(b, p);
    adj[b][c].emplace_back(a, p);
    ctotal[a][c] += p;
    ctotal[b][c] += p;
  }

  priority_queue<tuple<ll, int, int>, vector<tuple<ll, int, int>>, greater< >> pq;
  pq.emplace(0, 1, 0);
  auto update = [&](int b, int c, ll d) {
    if(!cost[b].count(c) || d < cost[b][c]) {
      cost[b][c] = d;
      pq.emplace(d, b, c);
    }
  };

  while (!pq.empty()) {
    auto[d, a, c] = pq.top();
    pq.pop();

    if(cost[a][c] != d) continue;
    if (c == 0) {
      for(auto& [color, cedges]: adj[a]) {
        for(auto& [b, p] : cedges) {
          update(b, 0, d + ctotal[a][color] - p);
          update(b, 0, d + p);
          update(b, color, d);
        }
      }
    } else {
      for(auto& [b, p] : adj[a][c])
        update(b, 0, d + ctotal[a][c] - p);
    }
  }

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

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