Submission #734256

#	Time	Username	Problem	Language	Result	Execution time	Memory
734256		asdfgrace	Robot (JOI21_ho_t4)	C++17	100 / 100	933 ms	127016 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define DEBUG(x) //x
#define A(x) DEBUG(assert(x))
#define PRINT(x) DEBUG(cerr << x)
#define PV(x) DEBUG(cerr << #x << " = " << x << endl)
#define PAR(x) DEBUG(PRINT(#x << " = { "); for (auto y : x) PRINT(y << ' '); PRINT("}\n");)
#define PAR2(x) DEBUG(PRINT(#x << " = { "); for (auto [y, z] : x) PRINT(y << ',' << z << "  "); PRINT("}\n");)
typedef int64_t i64;
const i64 INF = i64(1e18); //1000000007; //998244353;


struct S {
  int n, m;
  vector<unordered_map<i64, set<pair<i64, i64>>>> edges;
  vector<unordered_map<i64, i64>> csum;

  void run() {
    cin >> n >> m;
    edges.resize(n);
    csum.resize(n);
    for (int i = 0; i < m; ++i) {
      i64 a, b, c, p;
      cin >> a >> b >> c >> p;
      --a; --b;
      edges[a][c].insert({b, p});
      edges[b][c].insert({a, p});
      csum[a][c] += p;
      csum[b][c] += p;
    }
    
    int ii = 0;
    for (auto node : edges) {
      PV(ii++);
      for (auto [id, s] : node) {
        PV(id); PAR2(s);
      }
    }
    
    vector<i64> d(n, INF);
    vector<unordered_map<i64, i64>> d2(n);
    d[0] = 0;
    priority_queue<array<i64, 3>> q;
    q.push({0, 0, 0});
    
    while (!q.empty()) {
      PAR(q.top());
      i64 dist = -q.top()[0];
      i64 node = q.top()[1];
      i64 c = q.top()[2];
      q.pop();
      if (c) {
        // you must only push "exclude the rest" into the queue
        // d[node] = min(d[node], d2[node][c]);
        if (d2[node][c] != dist) continue;
        for (auto [next, wt] : edges[node][c]) {
          i64 rest = d2[node][c] + csum[node][c] - wt;
          if (rest < d[next]) {
            d[next] = rest;
            q.push({-rest, next, 0});
          }
        }
      } else {
        if (d[node] != dist) continue;
        for (auto &[color, adj] : edges[node]) {
          assert(color != 0);
          for (auto [next, wt] : adj) {
            assert(next >= 0 && next < n);
            assert(csum[node].count(color));
            i64 rest = d[node] + csum[node][color] - wt;
            if (rest < d[next]) {
              d[next] = rest;
              q.push({-rest, next, 0});
            }
            if (d[node] + wt < d[next]) {
              d[next] = d[node] + wt;
              q.push({-d[node] - wt, next, 0});
            }
            if (!d2[next].count(color) || dist < d2[next][color]) {
              d2[next][color] = dist;
              q.push({-dist, next, color});
            }
          }
        }
      }
    }
    
    for (auto a : d2) {
      PAR2(a);
    }
    PAR(d);
    cout << (d[n - 1] >= INF ? -1 : d[n - 1]) << '\n';
  }
};

int main() {
  ios::sync_with_stdio(0); cin.tie(0);
  auto sol = make_unique<S>();
  sol->run();
}

Compilation message (stderr)

Main.cpp: In member function 'void S::run()':
Main.cpp:32:9: warning: unused variable 'ii' [-Wunused-variable]
   32 |     int ii = 0;
      |         ^~

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