結果

問題 No.3013 ハチマキ買い星人
コンテスト
ユーザー Lidelie
提出日時 2025-02-02 15:43:29
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 1,668 bytes
コンパイル時間 4,529 ms
コンパイル使用メモリ 285,420 KB
実行使用メモリ 37,548 KB
最終ジャッジ日時 2025-02-02 15:44:58
合計ジャッジ時間 88,070 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 20 TLE * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <algorithm>
#define space " "
#define big 2000000000000000000
using namespace std;
using ll = long long;

class weighted_graph{
    private:
    public:
    //vector<ll> _node;
    ll _node;
    vector<vector<pair<ll,ll>>> _e;//pair:<to,cost>
    void add_edge(ll a,ll b,ll cost){
        _e[a].push_back(make_pair(b,cost));
        _e[b].push_back(make_pair(a,cost));
    }
    void add_directed_edge(ll from,ll to,ll cost){
        _e[from].push_back(make_pair(to,cost));
    }
    vector<ll> dijkstra(ll start){
        priority_queue<pair<ll,ll>> pq;
        pq.push(make_pair(0,start));
        vector<ll> cost(_node,big);
        cost[0]=0;
        while(pq.size()>0){
            ll cur;
            tie(ignore,cur) = pq.top();
            pq.pop();
            for(auto i : _e[cur]){//pair<ll,ll> i:<to,cost>
                if(cost[cur]+i.second < cost[i.first]){
                    cost[i.first]=cost[cur]+i.second;
                    pq.push(make_pair(cost[cur]+i.second,i.first));
                }
            }
        }
        return cost;
    }

    weighted_graph(ll node_count){
        //_node = vector<ll>(n);
        _node = node_count;
        _e = vector<vector<pair<ll,ll>>>(node_count);
    }
};
int main(){
    ll n,m,p,y;
    cin >> n >> m >> p >> y;
    weighted_graph g(n);
    for(ll i = 0;i<m;i++){
        ll a,b,c;
        cin >> a >> b >> c;
        a--;b--;
        g.add_edge(a,b,c);
    }
    auto cost = g.dijkstra(0);
    ll ans = 0;
    for(ll i = 0;i<p;i++){
        ll d,e;
        cin >> d >> e;
        d--;
        ans = max(ans,max((ll)0,y-cost[d])/e);
    }
    cout << ans << endl;
}
0