結果
問題 |
No.3013 ハチマキ買い星人
|
ユーザー |
![]() |
提出日時 | 2025-01-25 14:14:34 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,233 bytes |
コンパイル時間 | 9,162 ms |
コンパイル使用メモリ | 269,180 KB |
実行使用メモリ | 20,764 KB |
最終ジャッジ日時 | 2025-01-25 23:12:37 |
合計ジャッジ時間 | 20,448 ms |
ジャッジサーバーID (参考情報) |
judge6 / judge7 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 27 WA * 18 |
ソースコード
#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, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> que; que.push(make_pair(0, 1)); vector<long long> kakutei(N + 1, -1); while (que.size() > 0) { pair<long long, int> tmp = que.top(); que.pop(); if (kakutei[tmp.second] == -1) { 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 = max((long long)0, Y - kakutei[D[i]]); ans = max(ans, tmp / E[i]); } cout << ans << endl; return 0; }