結果
問題 | No.3013 ハチマキ買い星人 |
ユーザー |
![]() |
提出日時 | 2025-01-25 14:02:51 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,107 bytes |
コンパイル時間 | 1,137 ms |
コンパイル使用メモリ | 85,648 KB |
実行使用メモリ | 18,472 KB |
最終ジャッジ日時 | 2025-01-25 23:06:03 |
合計ジャッジ時間 | 14,457 ms |
ジャッジサーバーID (参考情報) |
judge8 / judge11 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 7 WA * 17 RE * 21 |
ソースコード
#include <iostream>#include <vector>#include <queue>int main(){long long N, M, P, Y;std::cin >> N >> M >> P >> Y;std::vector<std::vector<std::pair<int, int>>> graph(N);int D[P], E[P];for(int i = 0, a, b, c; i < N; ++i){std::cin >> a >> b >> c; a--, b--;graph[a].emplace_back(b, c);graph[b].emplace_back(a, c);}for(int i = 0; i < P; ++i){std::cin >> D[i] >> E[i]; D[i]--;}std::vector<long long> distance(N, -0x4000000000000000); distance[0] = 0;std::vector<char> already(N, false);std::priority_queue<std::pair<long long, int>> search;search.push({0, 0});while(search.size() > 0){auto p = search.top();search.pop();if(already[p.second]) continue;already[p.second] = true;for(auto q : graph[p.second]){if(p.first - q.second > distance[q.first]){distance[q.first] = p.first - q.second;search.push({distance[q.first], q.first});}}}long long ans = 0;for(int i = 0; i < P; ++i){long long zankin = Y + distance[D[i]];if(zankin > 0){ans = std::max(ans, zankin / E[i]);}}std::cout << ans << std::endl;return 0;}