Submission #530533

#	Time	Username	Problem	Language	Result	Execution time	Memory
530533		Alex_tz307	Robot (JOI21_ho_t4)	C++17	100 / 100	895 ms	101108 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int kN = 1e5;
unordered_map<int, vector<pair<int, int>>> g[1 + kN];
unordered_map<int, int64_t> sum[1 + kN], dp[1 + kN];

void testCase() {
  int n, m;
  cin >> n >> m;
  for (int i = 0; i < m; ++i) {
    int u, v, c, w;
    cin >> u >> v >> c >> w;
    g[u][c].emplace_back(v, w);
    g[v][c].emplace_back(u, w);
    sum[u][c] += w;
    sum[v][c] += w;
  }
  priority_queue<tuple<int64_t, int, int>, vector<tuple<int64_t, int, int>>, greater<tuple<int64_t, int, int>>> pq;
  dp[1][0] = 0;
  pq.emplace(0, 1, 0);
  while (!pq.empty()) {
    int64_t cost;
    int u, c;
    tie(cost, u, c) = pq.top();
    pq.pop();
    if (cost != dp[u][c]) {
      continue;
    }
    if (c == 0) {
      for (auto itr : g[u]) {
        int c = itr.first;
        for (auto it : itr.second) {
          int v, w;
          tie(v, w) = it;
          if (!dp[v].count(c) || dp[v][c] > cost) {
            dp[v][c] = cost;
            pq.emplace(cost, v, c);
          }
          if (!dp[v].count(0) || dp[v][0] > cost + min((int64_t)w, sum[u][c] - w)) {
            dp[v][0] = cost + min((int64_t)w, sum[u][c] - w);
            pq.emplace(dp[v][0], v, 0);
          }
        }
      }
    } else {
      for (auto it : g[u][c]) {
        int v, w;
        tie(v, w) = it;
        if (!dp[v].count(0) || dp[v][0] > cost + sum[u][c] - w) {
          dp[v][0] = cost + sum[u][c] - w;
          pq.emplace(dp[v][0], v, 0);
        }
      }
    }
  }
  if (!dp[n].count(0)) {
    cout << "-1\n";
  } else {
    cout << dp[n][0] << '\n';
  }
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int tests = 1;
  for (int tc = 0; tc < tests; ++tc) {
    testCase();
  }
  return 0;
}

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