結果
問題 | No.3013 ハチマキ買い星人 |
ユーザー |
![]() |
提出日時 | 2025-01-25 13:59:43 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 468 ms / 2,000 ms |
コード長 | 1,759 bytes |
コンパイル時間 | 3,680 ms |
コンパイル使用メモリ | 286,580 KB |
実行使用メモリ | 27,204 KB |
最終ジャッジ日時 | 2025-01-25 23:05:02 |
合計ジャッジ時間 | 15,916 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge10 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 45 |
ソースコード
//#define _GLIBCXX_DEBUG#include <bits/stdc++.h>using namespace std;#define rep(i, n) for (int i = 0; i < (ll)(n); i++)#define all(a) (a).begin(), (a).end()using ll = long long;const int INF32 = 2e9;const ll INF64 = 4e18;int main() {// 入力.ll N, M, P, Y;cin >> N >> M >> P >> Y;vector<ll> A(M), B(M), C(M), E(N, INF64);vector<vector<pair<ll, ll>>> G(N);for (int i = 0; i < M; i++) {cin >> A[i] >> B[i] >> C[i];A[i]--;B[i]--; // 0-indexed.G[A[i]].push_back(make_pair(B[i], C[i]));G[B[i]].push_back(make_pair(A[i], C[i]));}for (int i = 0; i < P; i++) {ll Di, EDi;cin >> Di >> EDi;Di--;// 0-indexed.E[Di] = EDi;}// ダイクストラ法に必要な配列等.vector<ll> katsuage(N, INF64);vector<bool> confirmed(N, false);priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>>PQ;// 始点.katsuage[0] = 0;PQ.push(make_pair(katsuage[0], ll(0)));// ダイクストラ法.while (!PQ.empty()) {int pos = PQ.top().second;PQ.pop();if (confirmed[pos])continue;confirmed[pos] = true;for (int i = 0; i < G[pos].size(); i++) {int next = G[pos][i].first;int cost = G[pos][i].second;if (katsuage[next] > katsuage[pos] + cost) {katsuage[next] = katsuage[pos] + cost;PQ.push(make_pair(katsuage[next], ll(next)));}}}// ハチマキが何本買えるか.ll ans = 0;for (int i = 0; i < N; i++) {ans = max(ans, (Y-katsuage[i])/E[i]);}cout << ans << endl;return 0;}