Submission #12401080


Source Code Expand

Copy
#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

Submission Time
Task E - Two Currencies
User niuez
Language C++ (GCC 9.2.1)
Score 500
Code Size 2575 Byte
Status
Exec Time 40 ms
Memory 7340 KB

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

Set Name Sample All
Score / Max Score 0 / 0 500 / 500
Status
× 5
× 27
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, sample_05.txt
All line_1.txt, line_2.txt, random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_07.txt, random_08.txt, random_09.txt, random_10.txt, random_11.txt, random_12.txt, random_13.txt, random_14.txt, random_15.txt, random_16.txt, random_17.txt, random_18.txt, random_19.txt, random_20.txt, sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, sample_05.txt
Case Name Status Exec Time Memory
line_1.txt 14 ms 4088 KB
line_2.txt 13 ms 4132 KB
random_01.txt 38 ms 5820 KB
random_02.txt 35 ms 7340 KB
random_03.txt 36 ms 5664 KB
random_04.txt 40 ms 5816 KB
random_05.txt 37 ms 5848 KB
random_06.txt 38 ms 5772 KB
random_07.txt 35 ms 5684 KB
random_08.txt 34 ms 5788 KB
random_09.txt 33 ms 5812 KB
random_10.txt 38 ms 5964 KB
random_11.txt 36 ms 5948 KB
random_12.txt 35 ms 5848 KB
random_13.txt 38 ms 5908 KB
random_14.txt 33 ms 5912 KB
random_15.txt 30 ms 5064 KB
random_16.txt 37 ms 5876 KB
random_17.txt 36 ms 7296 KB
random_18.txt 36 ms 5748 KB
random_19.txt 33 ms 4956 KB
random_20.txt 34 ms 5748 KB
sample_01.txt 2 ms 3684 KB
sample_02.txt 4 ms 3632 KB
sample_03.txt 5 ms 3680 KB
sample_04.txt 4 ms 3648 KB
sample_05.txt 3 ms 3692 KB