結果
問題 | No.3013 ハチマキ買い星人 |
ユーザー |
![]() |
提出日時 | 2025-01-25 13:36:26 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 194 ms / 2,000 ms |
コード長 | 1,560 bytes |
コンパイル時間 | 3,323 ms |
コンパイル使用メモリ | 286,496 KB |
実行使用メモリ | 22,388 KB |
最終ジャッジ日時 | 2025-01-25 22:52:28 |
合計ジャッジ時間 | 9,480 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 45 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; #ifdef LOCAL #include <debug.hpp> #else #define debug(...) #endif // 到達不可: -1 template <class T> vector<T> dijkstra(const vector<vector<pair<int, T>>>& G, int start = 0) { int N = G.size(); vector<T> dist(N, T(-1)); priority_queue<pair<T, int>, vector<pair<T, int>>, greater<pair<T, int>>> que; dist[start] = 0; que.emplace(dist[start], start); while (!que.empty()) { auto [expected, from] = que.top(); que.pop(); // 最短距離でない場合, continue if (dist[from] < expected) continue; for (auto&& [to, cost] : G[from]) { if (dist[to] == T(-1) || dist[to] > dist[from] + cost) { dist[to] = dist[from] + cost; que.emplace(dist[to], to); } } } return dist; } int main() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(20); ll N, M, P, Y; cin >> N >> M >> P >> Y; vector<vector<pair<int, ll>>> G(N); for (int i = 0; i < M; i++) { int A, B; ll C; cin >> A >> B >> C; A--, B--; G[A].emplace_back(B, C); G[B].emplace_back(A, C); } vector<ll> D(P), E(P); for (int i = 0; i < P; i++) cin >> D[i] >> E[i], D[i]--; auto dist = dijkstra(G, 0); ll ans = 0; for (int i = 0; i < P; i++) { if (dist[D[i]] == -1) continue; ans = max(ans, max(0LL, (Y - dist[D[i]])) / E[i]); } cout << ans << "\n"; }