제출 #1303714

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1303714		kunzaZa183	Robot (JOI21_ho_t4)	C++20	24 / 100	957 ms	130516 KiB

Main

#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);
  vector<map<int, vector<pair<int, int>>>> spe(n);
  vector<map<int, int>> per(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});
    spe[u][col].emplace_back(v, w), spe[v][col].emplace_back(u, w);
    per[u][col] += w, per[v][col] += w;
  }

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

  priority_queue<array<int, 4>, vector<array<int, 4>>, greater<array<int, 4>>>
      pqpii; // [w, cur, col, cos]

  pqpii.push({0, 0, m + 1, 0});
  const int bign = 1e18;
  vector<int> noc(n, bign);

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

    if (vsi[cur].count(col))
      continue;

    // cout << w << " " << cur << " " << col << " " << cos << "\n";

    vsi[cur][col] = w;

    int tot = per[cur][col];
    for (auto [tow, wew] : spe[cur][col]) {
      pqpii.push({w + max(0ll, tot - cos - wew), tow, m + 1, 0});
    }

    if (noc[cur] == bign) {
      noc[cur] = w;
      for (auto [tow, cow, wew] : adj[cur]) {
        pqpii.push({w + wew, tow, cow, wew});
        pqpii.push({w + per[cur][cow] - wew, tow, m + 1, 0});
      }
    }
  }

  int mini = noc[n - 1];
  for (auto [_, val] : vsi[n - 1]) {
    mini = min(mini, val);
  }

  if (mini == bign) {
    cout << "-1\n";
  } else {
    cout << mini << "\n";
  }
}

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