結果

問題 No.3013 ハチマキ買い星人
コンテスト
ユーザー Apollo@Kuro
提出日時 2025-01-23 17:19:31
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 420 ms / 2,000 ms
コード長 1,498 bytes
コンパイル時間 4,010 ms
コンパイル使用メモリ 285,604 KB
実行使用メモリ 21,584 KB
最終ジャッジ日時 2025-01-25 22:01:08
合計ジャッジ時間 16,087 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge9
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 45
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

// GPTによるBFS
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

// 定数
const ll INF = 1e18;

struct Edge {
    int to;
    ll cost;
};

int main() {
    // 入力
    int N, M, P;
    ll Y;
    cin >> N >> M >> P >> Y;

    vector<vector<Edge>> graph(N + 1);
    for (int i = 0; i < M; i++) {
        int A, B;
        ll C;
        cin >> A >> B >> C;
        graph[A].push_back({B, C});
        graph[B].push_back({A, C});
    }

    vector<int> D(P), E(P);
    for (int i = 0; i < P; i++) {
        cin >> D[i] >> E[i];
    }

    // BFSで最短距離を計算
    vector<ll> minCost(N + 1, INF);
    minCost[1] = 0;
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> pq;
    pq.push({0, 1});

    while (!pq.empty()) {
        auto [currentCost, u] = pq.top();
        pq.pop();

        if (currentCost > minCost[u]) continue;

        for (const auto &edge : graph[u]) {
            int v = edge.to;
            ll nextCost = max(0LL, currentCost + edge.cost);
            if (nextCost < minCost[v]) {
                minCost[v] = nextCost;
                pq.push({nextCost, v});
            }
        }
    }

    // パチマキの購入計算
    ll maxHachimaki = 0;
    for (int i = 0; i < P; i++) {
        int city = D[i];
        ll price = E[i];

        if (minCost[city] <= Y) {
            maxHachimaki = max(maxHachimaki, (Y - minCost[city]) / price);
        }
    }

    // 出力
    cout << maxHachimaki << endl;
    return 0;
}
0