Submission #992617

#	Time	Username	Problem	Language	Result	Execution time	Memory
992617		vjudge1	Robot (JOI21_ho_t4)	C++17	100 / 100	1508 ms	80884 KiB

Main

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

// #pragma GCC optimize ("O3")
// #pragma GCC optimize ("unroll-loops")

#ifdef LOCAL
  #include "algo/debug.h"
#else
  #define debug(...) 42
#endif

using ll = long long;
using db = long double; // or double, if TL is tight
#define int ll

// pairs
#define mp make_pair
#define f first
#define s second

// vectors
#define sz(v) (int)((v).size())
#define all(v) v.begin(), v.end()

int32_t main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  
  int n, m; cin >> n >> m;

  map<int, map<int, vector<pair<int, int>>>> adj;
  map<pair<int, int>, int> in; 
  for (int i = 0; i < m; i++) {
    int u, v, c, w; cin >> u >> v >> c >> w;
    adj[u][c].emplace_back(v, w);
    adj[v][c].emplace_back(u, w); 
    in[{u, c}] += w; in[{v, c}] += w; 
  }

  using T = tuple<int, int, int>;

  map<int, int> dp;
  map<pair<int, int>, int> dis;
  priority_queue<T, vector<T>, greater<T>> pq;
  pq.emplace(0, 1, 0); dis[{1, 0}] = 0;
  while (!pq.empty()) {
    auto [d, u, c] = pq.top(); pq.pop();
    
    if (c != 0) {
      if (dis.count({u, c}) && dis[{u, c}] != d)
        continue;
    
      for (auto &[v, w]: adj[u][c]) {
        int cost = in[{u, c}] - w;
        if (!dp.count(v) || dp[v] > d + cost) {
          dp[v] = d + cost;
          pq.emplace(dp[v], v, 0);
        }
      }
    } else {
      if (dp.count(u) && dp[u] != d) continue;

      for (auto &[c2, lAdj]: adj[u]) {
        for (auto &[v, w]: lAdj) {
          if (!dp.count(v) || dp[v] > in[{u, c2}] - w + d) {
            dp[v] = in[{u, c2}] - w + d;
            pq.emplace(dp[v], v, 0);
          }

          if (!dp.count(v) || dp[v] > d + w) {
            dp[v] = d + w;
            pq.emplace(dp[v], v, 0);
          }
 
          if (!dis.count({v, c2}) || dis[{v, c2}] > d) {
            dis[{v, c2}] = d;
            pq.emplace(dis[{v, c2}], v, c2);
          }
        }
      }
    }
  }

  cout << (dp.count(n) ? dp[n] : -1) << "\n";
} 

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