제출 #1298210

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1298210		kunzaZa183	Robot (JOI21_ho_t4)	C++20	34 / 100	3074 ms	212852 KiB

Main

#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main() {
  cin.tie(0)->sync_with_stdio(0);
  int n, m;
  cin >> n >> m;
  vector<vector<array<int, 3>>> adj(n);
  for (int i = 0; i < m; i++) {
    int u, v, col, w;
    cin >> u >> v >> col >> w;
    u--, v--;
    adj[u].push_back({v, col, w});
    adj[v].push_back({u, col, w});
  }

  for (int i = 0; i < n; i++) {
    sort(adj[i].begin(), adj[i].end());
    // cout << "I = " << i << "\n";
    // for (auto [to, col, w] : adj[i])
    //   cout << to << " " << col << " " << w << "\n";
  }

  priority_queue<array<int, 3>, vector<array<int, 3>>, greater<array<int, 3>>>
      pqpii; // [w, cur, par]

  pqpii.push({0, 0, -1});
  const int bign = 1e18;
  vector<vector<int>> visited(n);
  for (int i = 0; i < n; i++) {
    visited[i] = vector<int>(adj[i].size(), bign);
  }
  vector<int> neg1(n, bign);

  vector<map<int, int>> vmii(n);

  for (int i = 0; i < n; i++) {
    for (auto [to, col, w] : adj[i]) {
      vmii[i][col] += w;
    }
  }

  while (!pqpii.empty()) {
    auto [w, cur, par] = pqpii.top();
    pqpii.pop();

    // cout << w << " " << cur << " " << par << "\n";

    if (par == -1) {
      if (neg1[cur] != bign)
        continue;

      neg1[cur] = w;

      for (int i = 0; i < adj[cur].size(); i++) {
        // cout << cur << " " << i << " " << to << " " << col << " " << len <<
        // "\n";
        if (i == par)
          continue;

        auto [to, col, len] = adj[cur][i];
        int in = lower_bound(adj[to].begin(), adj[to].end(),
                             array<int, 3>({cur, -1, -1})) -
                 adj[to].begin();
        if (visited[to][in] == bign) {
          // cout << cur << " " << i << " " << to << " " << col << " " << len
          //      << "\n";
          pqpii.push({w + len, to, in});
        }
        if (neg1[to] == bign) {
          pqpii.push({vmii[cur][col] - len + w, to, -1});
        }
      }
    } else {
      if (visited[cur][par] != bign) {
        continue;
      }

      visited[cur][par] = w;

      for (int i = 0; i < adj[cur].size(); i++) {
        // cout << cur << " " << i << " " << to << " " << col << " " << len <<
        // "\n";
        if (i == par)
          continue;

        auto [to, col, len] = adj[cur][i];
        int in = lower_bound(adj[to].begin(), adj[to].end(),
                             array<int, 3>({cur, -1, -1})) -
                 adj[to].begin();
        if (visited[to][in] == bign) {
          // cout << cur << " " << i << " " << to << " " << col << " " << len
          //      << "\n";
          pqpii.push({w + len, to, in});
        }
        if (neg1[to] == bign) {
          if (col != adj[cur][par][1]) {
            pqpii.push({vmii[cur][col] - len + w, to, -1});
          } else {
            pqpii.push({vmii[cur][col] - len - adj[cur][par][2] + w, to, -1});
          }
        }
      }
    }
  }

  int mini = neg1[n - 1];
  for (int i = 0; i < visited[n - 1].size(); i++) {
    mini = min(mini, visited[n - 1][i]);
  }
  if (mini == bign) {
    cout << "-1\n";
  } else {
    cout << mini << "\n";
  }
}

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