Language: C++

#include<iostream>
#include<string>

void solve_A() {
	int S, W;
	std::cin >> S >> W;
	//std::string result = (S <= W ? "unsafe" : "safe");
	std::cout << (S <= W ? "unsafe" : "safe") << std::endl;
}

void solve_B() {
	int A, B, C, D;
	std::cin >> A >> B >> C >> D;
	while (!( A <= 0 || C <= 0)) {
		C -= B;
		if (C <= 0) break;
		A -= D;
	}
	std::cout << (A <= 0 ? "No" : "Yes") << std::endl;
}

#include<vector>
#include<algorithm>

void solve_C() {
	int N;
	std::vector<std::string> v;
	std::cin >> N;
	for (int i = 0; i < N; i++) {
		std::string tmp;
		std::cin >> tmp;
		v.push_back(tmp);
	}
	std::sort(v.begin(), v.end());
	auto last = std::unique(v.begin(), v.end());
	v.erase(last, v.end());
	std::cout << v.size() << std::endl;

}

#include<set>

void solve_C2() {
	int N;
	std::set<std::string> st;
	std::cin >> N;
	for (int i = 0; i < N; i++) {
		std::string s;
		std::cin >> s;
		st.insert(s);
	}
	std::cout << st.size() << std::endl;
}

void solve_D() {//TLE
	std::string S;
	std::cin >> S;
	int N = S.length();
	int ans = 0;
	for (int i = 0; i < N-3; i++) {
		for (int j = i+3; j < N; j++) {
			int num = atoi(S.substr(i, j - i+1).c_str());
			if (num % 2019 == 0) {
				ans++;
			}
		}
	}
	std::cout << ans << std::endl;
}

void solve_D2() {//類題158E
	std::string s;
	std::cin >> s;
	int n = s.size();
	std::reverse(s.begin(), s.end());
	int x = 1, ans = 0, total = 0;//累積和
	const int m = 2019;
	std::vector<int> cnt(m);
	for (int i = 0; i < n; i++) {
		cnt[total]++;
		total += atoi(s.substr(i, 1).c_str()) * x; //N桁までの値 = N桁目の値 * 10^N + N-1桁目の値
		total %= m; //N桁までの値のmod = (N桁 + (N-1~1)桁目のmod) mod 2019
		ans += cnt[total];//計算したN桁の累積和のmodの値が1~N-1桁までで計算したmodと一致する場合、区間の数値のmodが0と同値
		//modが一致する個数の部分数列を新たに作成できるので、cnt配列の要素分足し合わせる
		x = x * 10 % m;
	}
	std::cout << ans << std::endl;
}

void solve_D3() {
	std::string s;
	std::cin >> s;
	int n = s.length();
	const int N = 200000;
	std::reverse(s.begin(), s.end());
	long long int x = 1, ans = 0;
	long long int total[N];//累積和
	total[0] = 0;
	const int m = 2019;
	std::vector<int> cnt(m);
	for (int i = 1; i <= n; i++) {
		total[i] = total[i-1] + atoi(s.substr(i, 1).c_str()) * x;
		x = x * 10;
		for (int j = 1; j < i-3; j++) {
			if ((total[i] - total[j])%2019 ==0) {
				ans++;
			}
		}
	}
	std::cout << ans << std::endl;
}

#include<queue>
const int MAX_V = 50;
const int MAX_S = MAX_V * 50 + 1;
const long long INF = 1e18;

struct Edge {
	int to, a, b;
	Edge(int to, int a, int b) :to(to), a(a), b(b) {}//コンストラクタ
};

struct Node {
	int v, s;//頂点、所持金
	long long x;//所要時間
	Node(int v, int s, long long x) :v(v), s(s), x(x) {}
	//bool operator < (const Node& a) const { return x > a.x; }//最小ヒープにする
};

std::vector<Edge> g[MAX_V];//隣接リスト
long long dp[MAX_V][MAX_S+1];

void solve_E() {
	int n, m, s;
	std::cin >> n >> m >> s;
	for (int i = 0; i<m; i++) {
		int u, v, a, b;
		std::cin >> u >> v >> a >> b;
		u--; v--;
		g[u].emplace_back(v, a, b);
		g[v].emplace_back(u, a, b);//双方向のノードの定義
	}
	std::vector<int> c(n), d(n);
	for (int i = 0; i < n; i++) {
		std::cin >> c[i] >> d[i];
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < MAX_S+1; j++) {
			dp[i][j] = INF;
		}
	}
	s = std::min(s, MAX_S);//ここが重要。消費する銀貨の最大値はA_max * (N_max - 1) = 50 * 49 = 2500
	//入力される銀貨がどんなに大きくてもここで最大値に丸める。そのあと、都市と銀貨の数について動的計画法を用いて最小の移動時間を計算する

	std::priority_queue<Node> q;
	auto push = [&]/*ラムダキャプチャ*/(int v, int s, long long x) {//ある地点にある所持金である時間で到達できる
		if (s < 0) return;//到達可能なノードのみを通す
		if (dp[v][s] <= x) return;//あるノード、ある所持金で到達するまでの時間が既に小さい場合は通さない
		dp[v][s] = x;
		q.emplace(v, s, x);
	};
	push(0, s, 0);//初期位置の定義
	while (!q.empty()) {
		Node node = q.top(); q.pop();//時間が最小のnodeの取得
		int v = node.v, s = node.s;
		long long x = node.x;
		//if (dp[v][s] != x) continue;//??状態については2回以上遷移をさせたくないらしい。だが、なくても実行速度は変わらない
		{
			int ns = std::min(s + c[v], MAX_S);
			push(v, ns, x + d[v]);//銀貨を増やす場合を追加
		}
		//銀貨を増やさない場合の辺をたどる遷移
		for (Edge edge: g[v]) {//範囲ベースfor
	 	push(edge.to, s - edge.a, x + edge.b);
		}
	}

	for (int i = 1; i < n; i++) {
		long long ans = INF;
		for (int j = 0; j < MAX_S; j++) {
			ans = std::min(ans, dp[i][j]);
		}
		std::cout << ans << std::endl;
	}

}


int main()
{
	//solve_A();
	//solve_B();
	//solve_C();
	//solve_D2();
	solve_E();
    return 0;
}


Compiler output:
In file included from /usr/include/c++/14/string:49,
                 from /usr/include/c++/14/bits/locale_classes.h:40,
                 from /usr/include/c++/14/bits/ios_base.h:41,
                 from /usr/include/c++/14/ios:44,
                 from /usr/include/c++/14/ostream:40,
                 from /usr/include/c++/14/iostream:41,
                 from a.cc:1:
/usr/include/c++/14/bits/stl_function.h: In instantiation of 'constexpr bool std::less<_Tp>::operator()(const _Tp&, const _Tp&) const [with _Tp = Node]':
/usr/include/c++/14/bits/predefined_ops.h:196:23:   required from 'bool __gnu_cxx::__ops::_Iter_comp_val<_Compare>::operator()(_Iterator, _Value&) [with _Iterator = __gnu_cxx::__normal_iterator<Node*, std::vector<Node, std::allocator<Node> > >; _Value = Node; _Compare = std::less<Node>]'
  196 |         { return bool(_M_comp(*__it, __val)); }
      |                       ~~~~~~~^~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_heap.h:140:48:   required from 'void std::__push_heap(_RandomAccessIterator, _Distance, _Distance, _Tp, _Compare&) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<Node*, vector<Node, allocator<Node> > >; _Distance = long int; _Tp = Node; _Compare = __gnu_cxx::__ops::_Iter_comp_val<less<Node> >]'
  140 |       while (__holeIndex > __topIndex && __comp(__first + __parent, __value))
      |                                          ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_heap.h:216:23:   required from 'void std::push_heap(_RAIter, _RAIter, _Compare) [with _RAIter = __gnu_cxx::__normal_iterator<Node*, vector<Node, allocator<Node> > >; _Compare = less<Node>]'
  216 |       std::__push_heap(__first, _DistanceType((__last - __first) - 1),
      |       ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  217 |                        _DistanceType(0), _GLIBCXX_MOVE(__value), __cmp);
      |                        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_queue.h:755:18:   required from 'void std::priority_queue<_Tp, _Sequence, _Compare>::emplace(_Args&& ...) [with _Args = {int&, int&, long long int&}; _Tp = Node; _Sequence = std::vector<Node, std::allocator<Node> >; _Compare = std::less<Node>]'
  755 |           std::push_heap(c.begin(), c.end(), comp);
      |           ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
a.cc:160:12:   required from here
  160 |                 q.emplace(v, s, x);
      |                 ~~~~~~~~~^~~~~~~~~
/usr/include/c++/14/bits/stl_function.h:405:20: error: no match for 'operator<' (operand types are 'const Node' and 'const Node')
  405 |       { return __x < __y; }
      |                ~~~~^~~~~
In file included from /usr/include/c++/14/string:48:
/usr/include/c++/14/bits/stl_iterator.h:448:5: note: candidate: 'template<class _Iterator> constexpr bool std::operator<(const reverse_iterator<_Iterator>&, const reverse_iterator<_Iterator>&)'
  448 |     operator<(const reverse_iterator<_Iterator>& __x,
      |     ^~~~~~~~
/usr/include/c++/14/bits/stl_iterator.h:448:5: note:   template argument deduction/substitution failed:
/usr/include/c++/14/bits/stl_function.h:405:20: note:   'const Node' is not derived from 'const std::reverse_iterator<_Iterator>'
  405 |       { return __x < __y; }
      |                ~~~~^~~~~
/usr/include/c++/14/bits/stl_iterator.h:493:5: note: candidate: 'template<class _IteratorL, class _IteratorR> constexpr bool std::operator<(const reverse_iterator<_Iterator>&, const reverse_iterator<_IteratorR>&)'
  493 |     operator<(const reverse_iterator<_IteratorL>& __x,
      |     ^~~~~~~~
/usr/include/c++/14/bits/stl_iterator.h:493:5: note:   template argument deduction/substitution failed:
/usr/include/c++/14/bits/stl_function.h:405:20: note:   'const Node' is not derived from 'const std::reverse_iterator<_Iterator>'
  405 |       { return __x < __y; }
      |                ~~~~^~~~~
/usr/include/c++/14/bits/stl_iterator.h:1694:5: note: candidate: 'template<class _IteratorL, class _IteratorR> constexpr bool std::operator<(const move_iterator<_IteratorL>&, const move_iterator<_IteratorR>&)'
 1694 |     operator<(const move_iterator<_IteratorL>& __x,
      |     ^~~~~~~~
/usr/include/c++/14/bits/stl_iterator.h:1694:5: note:   template argument deduction/substitution failed:
/usr/include/c++/14/bits/stl_function.h:405:20: note:   'const Node' is not derived from 'const std::move_iterator<_IteratorL>'
  405 |       { return __x < __y; }
      |                ~~~~^~~~~
/usr/include/c++/14/bits/stl_iterator.h:1760:5: note: candidate: 'template<class _Iterator> constexpr bool std::operator<(const move_iterator<_IteratorL>&, const move_iterator<_IteratorL>&)'
 1760 |     operator<(const move_iterator<_Iterator>& __x,
      |     ^~~~~~~~
/usr/include/c++/14/bits/stl_iterator.h:1760:5: note:   template argument deduction/substitution failed:
/usr/include/c++/14/bits/stl_function.h:405:20: note:   'const Node' is not derived from 'const std::move_iterator<_IteratorL>'
  405 |       { return __x < __y; }
      |                ~~~~^~~~~