Submission #12401080

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define rep(i,s,e) for(i64 (i) = (s);(i) < (e);(i)++)
#define all(x) x.begin(),x.end()

template<class T>
static inline std::vector<T> ndvec(size_t&& n, T val) noexcept {
  return std::vector<T>(n, std::forward<T>(val));
}

template<class... Tail>
static inline auto ndvec(size_t&& n, Tail&&... tail) noexcept {
  return std::vector<decltype(ndvec(std::forward<Tail>(tail)...))>(n, ndvec(std::forward<Tail>(tail)...));
}

template<class T, class Cond>
struct chain {
  Cond cond; chain(Cond cond) : cond(cond) {}
  bool operator()(T& a, const T& b) const {
    if(cond(a, b)) { a = b; return true; }
    return false;
  }
};
template<class T, class Cond>
chain<T, Cond> make_chain(Cond cond) { return chain<T, Cond>(cond); }

#include <vector>
#include <queue>

/*
 * delta(V v, fn (V t, W weight))
 * index(V v) -> int
 */
template<class V, class W, class Delta, class Index>
std::vector<W> dijkstra(std::size_t N, W inf, V s, Delta delta, Index index) {
  std::vector<W> dist(N, inf);
  using P = std::pair<W, V>;
  std::priority_queue<P, std::vector<P>, std::greater<P>> que;
  que.push({ dist[index(s)] = W(), s });
  while(!que.empty()) {
    W d = que.top().first;
    V v = que.top().second;
    que.pop();
    if(dist[index(v)] < d) continue;
    delta(v, [&](V t, W weight) {
        if(dist[index(t)] > dist[index(v)] + weight) {
          que.push({ dist[index(t)] = dist[index(v)] + weight, t });
        }
    });
  }
  return dist;
}

int main() {
  i64 N, M, S;
  cin >> N >> M >> S;
  S = std::min(S, 2500ll);

  struct edge {
    i64 to;
    i64 a;
    i64 b;
  };

  vector<vector<edge>> G(N);
  rep(i,0,M) {
    i64 u, v, a, b;
    cin >> u >> v >> a >> b;
    u--;
    v--;
    G[u].push_back({ v, a, b });
    G[v].push_back({ u, a, b });
  }

  vector<i64> C(N);
  vector<i64> D(N);
  rep(i,0,N) {
    cin >> C[i] >> D[i];
  }

  using P = std::pair<i64, i64>;
  auto index = [&](P p) { return p.first * 2501 + p.second; };
  auto delta = [&](P vv, auto func) {
    i64 v = vv.first;
    i64 c = vv.second;
    func(P(v, std::min(c + C[v], 2500ll)), D[v]);
    for(auto e: G[v]) {
      if(e.a <= c) {
        func(P(e.to, c - e.a), e.b);
      }
    }
  };
  auto res = dijkstra(N * 2501, (i64)(1e17), P(0, S), delta, index);
  rep(i,1,N) {
    i64 ans = res[index(P(i, 0))];
    rep(j,0,2501) {
      ans = std::min(ans, res[index(P(i, j))]);
    }
    cout << ans << "\n";
  }
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:4:28: warning: unnecessary parentheses in declaration of ‘i’ [-Wparentheses]
    4 | #define rep(i,s,e) for(i64 (i) = (s);(i) < (e);(i)++)
      |                            ^
./Main.cpp:67:3: note: in expansion of macro ‘rep’
   67 |   rep(i,0,M) {
      |   ^~~
./Main.cpp:4:28: warning: unnecessary parentheses in declaration of ‘i’ [-Wparentheses]
    4 | #define rep(i,s,e) for(i64 (i) = (s);(i) < (e);(i)++)
      |                            ^
./Main.cpp:78:3: note: in expansion of macro ‘rep’
   78 |   rep(i,0,N) {
      |   ^~~
./Main.cpp:4:28: warning: unnecessary parentheses in declaration of ‘i’ [-Wparentheses]
    4 | #define rep(i,s,e) for(i64 (i) = (s);(i) < (e);(i)++)
      |                            ^
./Main.cpp:95:3: note: in expansion of macro ‘rep’
   95 |   rep(i,1,N) {
      |   ^~~
./Main.cpp:4:28: warning: unnecessary parentheses in declaration of ‘j’ [-Wparentheses]
    4 | #define rep(i,s,e) for(i64 (i) = (s);(i) < (e);(i)++)
      |                            ^
./Main.cpp:97:5: note: in expansion of macro ‘rep’
   97 |     rep(j,0,2501) {
      |     ^~~

Judge Result