Submission #859888

#	Time	Username	Problem	Language	Result	Execution time	Memory
859888		NeroZein	Robot (JOI21_ho_t4)	C++17	100 / 100	850 ms	96312 KiB

Main

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

#ifdef Nero
#include "Deb.h"
#else
#define deb(...)
#endif

using arr = array<long long, 3>;

const int N = 1e5 + 5;

map<int, long long> ps[N]; 
map<int, long long> dp[N]; 
vector<array<int, 3>> g[N]; 
map<int, vector<pair<int, int>>> mp[N];//v, c 

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n, m;
  cin >> n >> m;
  for (int i = 0; i < m; ++i) {
    int u, v, c, w;
    cin >> u >> v >> c >> w;
    ps[v][c] += w;
    ps[u][c] += w; 
    mp[v][c].emplace_back(u, w);
    mp[u][c].emplace_back(v, w);
    g[u].push_back({v, w, c});
    g[v].push_back({u, w, c});
  }
  priority_queue<arr, vector<arr>, greater<arr>> pq;
  dp[1][0] = 0; 
  pq.push({0, 0, 1}); 
  while (!pq.empty()) {
    auto [cost, color, v] = pq.top();
    pq.pop();
    //deb(v) deb(color) deb(cost) cout << '\n';
    if (dp[v][color] < cost) {
      continue;
    }
    if (v == n && !color) {
      cout << cost << '\n';
      return 0; 
    }
    if (color) {
      for (auto [u, w] : mp[v][color]) {
        long long pay = cost;
        pay += ps[v][color] - w;
        if (!dp[u].count(0) || dp[u][0] > pay) {
          dp[u][0] = pay;
          pq.push({pay, 0, u}); 
        }                  
      }
    } else {
      for (auto [u, w, c] : g[v]) {
        long long pay = cost;
        if (!dp[u].count(c) || dp[u][c] > pay) {
          dp[u][c] = pay;
          pq.push({pay, c, u}); 
        }
        pay += min((long long) w, ps[v][c] - w);
        if (!dp[u].count(0) || dp[u][0] > pay) {
          dp[u][0] = pay;
          pq.push({pay, 0, u});
        }
      }
    }

  }
  cout << -1 << '\n'; 
  return 0;
}

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