結果
問題 |
No.3013 ハチマキ買い星人
|
ユーザー |
![]() |
提出日時 | 2025-01-25 13:53:14 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
MLE
|
実行時間 | - |
コード長 | 1,155 bytes |
コンパイル時間 | 9,531 ms |
コンパイル使用メモリ | 269,772 KB |
実行使用メモリ | 1,088,576 KB |
最終ジャッジ日時 | 2025-01-25 23:03:06 |
合計ジャッジ時間 | 63,763 ms |
ジャッジサーバーID (参考情報) |
judge6 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 6 WA * 19 TLE * 9 MLE * 11 |
ソースコード
#include <bits/stdc++.h> using namespace std; int main() { int N, M, P; long long Y; cin >> N >> M >> P >> Y; vector<int> A(M), B(M), C(M), D(P), E(P); vector<vector<pair<int, int>>> g(N + 1); for (int i = 0; i < M; ++i) { cin >> A[i] >> B[i] >> C[i]; 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) cin >> D[i] >> E[i]; priority_queue<pair<long long, long long>, vector<pair<long long, long long>>, greater<pair<long long, long long>>> que; que.push(make_pair(0, 1)); vector<long long> kakutei(N + 1, -1); while (que.size() > 0) { pair<long long, long long> tmp = que.top(); que.pop(); kakutei[tmp.second] = tmp.first; for (auto x : g[tmp.second]) { if (kakutei[x.first] == -1) que.push(make_pair(tmp.first + x.second, x.first)); } } long long ans = 0; for (int i = 0; i < P; ++i) { long long tmp = Y - kakutei[D[i]]; ans = max(ans, tmp / E[i]); } cout << ans << endl; return 0; }