Submission #1157112

#	Time	Username	Problem	Language	Result	Execution time	Memory
1157112		fryingduc	Robot (JOI21_ho_t4)	C++20	100 / 100	536 ms	71440 KiB

Main

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

#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)
#endif

const int maxn = 6e5 + 5;
int n, m;
vector<pair<int, long long>> g[maxn];
int eu[maxn], ev[maxn], ec[maxn], ep[maxn];
long long d[maxn];
long long s[maxn];
map<pair<int, int>, int> mp;
int total_id;

void add(int u, int c, int p) {
  if (!mp.count(make_pair(u, c))) {
    mp[make_pair(u, c)] = ++total_id;
  }
  s[mp[make_pair(u, c)]] += p;
}

void solve() {
  cin >> n >> m;
  total_id = n;
  for (int i = 1; i <= m; ++i) {
    cin >> eu[i] >> ev[i] >> ec[i] >> ep[i];
    add(eu[i], ec[i], ep[i]);
    add(ev[i], ec[i], ep[i]);
  }
  for (int i = 1; i <= m; ++i) {
    int u = eu[i], v = ev[i];
    int x = mp[make_pair(eu[i], ec[i])], y = mp[make_pair(ev[i], ec[i])];
    // change (u, v, c) or every edge with same color except (u, v, c)
    g[u].emplace_back(v, min((long long) ep[i], s[x] - ep[i]));
    g[v].emplace_back(u, min((long long) ep[i], s[y] - ep[i]));
    // go directly to (u, v, c)
    g[u].emplace_back(y, 0);
    g[v].emplace_back(x, 0);
    // adding the cost of the previous edge in case we haven't
    g[x].emplace_back(v, s[x] - ep[i]);
    g[y].emplace_back(u, s[y] - ep[i]);
  }
  memset(d, 0x3f, sizeof(d));
  d[1] = 0;
  using T = pair<long long, int>;
  priority_queue<T, vector<T>, greater<T>> pq;
  pq.push(make_pair(0, 1));
  while (!pq.empty()) {
    long long dist; int u;
    tie(dist, u) = pq.top();
    pq.pop();
    if (dist > d[u]) {
      continue;
    }    
    for (auto e:g[u]) {
      int v; long long w;
      tie(v, w) = e;
      if (d[v] > d[u] + w) {
        pq.push(make_pair(d[v] = d[u] + w, v));
      }
    }
  }
  cout << (d[n] > 1e17 ? -1 : d[n]); 
}

signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  solve();

  return 0;
}

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