結果

問題 No.3013 ハチマキ買い星人
ユーザー Shizen
提出日時 2025-01-25 20:35:20
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,075 bytes
コンパイル時間 4,141 ms
コンパイル使用メモリ 172,524 KB
実行使用メモリ 19,712 KB
最終ジャッジ日時 2025-01-26 00:07:39
合計ジャッジ時間 17,076 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge7
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 11 WA * 11 RE * 23
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:30:13: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions]
   30 |         auto[cst,pos] = que.top();
      |             ^
main.cpp:34:17: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions]
   34 |         for(auto[x,c]:path[pos]){
      |                 ^

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template<typename T> using p_que = priority_queue<T,vector<T>,greater<T>>;
ll inf = (1LL<<60);

int main(){
    int n,m,p;
    ll mny;
    cin >> n >> m >> p >> mny;

    vector<vector<pair<int,ll>>>path (n,vector<pair<int,ll>>(0));
    for(int i=0;i<m;i++){
        int x,y;
        ll c;
        cin >> x >> y >> c;
        x--,y--;

        path[x].push_back({y,c});
        path[y].push_back({x,c});
    }

    vector<ll>mp (n,inf);
    mp[0] = 0;

    p_que<pair<ll,int>>que;
    que.push({0,0});

    while(!que.empty()){
        auto[cst,pos] = que.top();
        que.pop();
        if(cst != mp[pos]) continue;

        for(auto[x,c]:path[pos]){
            if(mp[x] > c + mp[pos]){
                mp[x] = c + mp[pos];
                que.push({x,mp[x]});
            }
        }
    }

    ll ans = 0;
    for(int i=0;i<p;i++){
        int x;
        ll c;
        cin >> x >> c;
        x--;

        ll rm = max(0LL,mny - mp[x]);

        ans = max(ans,rm / c);
    }

    cout << ans << endl;
}
0