Submission #624983

#	Time	Username	Problem	Language	Result	Execution time	Memory
624983		MilosMilutinovic	Ceste (COCI17_ceste)	C++14	160 / 160	956 ms	24396 KiB

ceste

/**
 *    author:  wxhtzdy
 *    created: 09.08.2022 10:15:44
**/
#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);  
  int n, m;
  cin >> n >> m;
  vector<vector<array<int, 3>>> g(n);
  for (int i = 0; i < m; i++) {
    int x, y, t, c;
    cin >> x >> y >> t >> c;
    --x; --y;
    g[x].push_back({y, t, c});
    g[y].push_back({x, t, c}); 
  }
  vector<set<pair<int, int>>> dist(n);
  dist[0].insert({0, 0});
  set<array<int, 3>> st;
  st.insert({0, 0, 0}); 
  auto Update = [&](int v, int t, int c) {
    auto it = dist[v].lower_bound({t, c});    
    while (it != dist[v].end()) {
      if (it->first >= t && it->second >= c) {
        if (st.find({v, it->first, it->second}) != st.end()) {
          st.erase(st.find({v, it->first, it->second}));
        }
        it = dist[v].erase(it);
      } else {
        break;
      }
    }
    it = dist[v].lower_bound({t, c});             
    if (it != dist[v].begin()) {
      it = prev(it);           
      if (it->first < t && it->second > c) {
        dist[v].emplace(t, c);
        st.insert({t, c, v});
      }
    } else {
      dist[v].emplace(t, c);
      st.insert({t, c, v});
    }
  };
  while (!st.empty()) {
    auto it = st.begin();
    int t = (*it)[0];
    int c = (*it)[1]; 
    int u = (*it)[2];
    st.erase(it);
    for (auto& p : g[u]) {
      Update(p[0], t + p[1], c + p[2]);
    }
  }
  for (int i = 1; i < n; i++) {
    if (dist[i].empty()) {
      cout << -1 << '\n';
    } else {
      long long ans = 1e18;
      for (auto& p : dist[i]) {
        ans = min(ans, p.first * 1LL * p.second);
      }
      cout << ans << '\n';
    }
  }                         
  return 0;
}

• Subtask 1: 16 / 16
• Subtask 2: 16 / 16
• Subtask 3: 16 / 16
• Subtask 4: 16 / 16
• Subtask 5: 16 / 16
• Subtask 6: 16 / 16
• Subtask 7: 16 / 16
• Subtask 8: 16 / 16
• Subtask 9: 16 / 16
• Subtask 10: 16 / 16