結果

問題 No.3013 ハチマキ買い星人
ユーザー shingo0909
提出日時 2025-01-25 13:16:36
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 474 ms / 2,000 ms
コード長 2,227 bytes
コンパイル時間 3,813 ms
コンパイル使用メモリ 288,940 KB
実行使用メモリ 21,724 KB
最終ジャッジ日時 2025-01-25 22:41:17
合計ジャッジ時間 15,842 ms
ジャッジサーバーID
（参考情報） 		judge8 / judge11
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 45
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <cstdlib>
#include <math.h>

using namespace std;
using ll = long long;

//Edge
struct Edge{
    int to;
    long long cost;
};

//Dijkstra
class dijkstra{
public:
    vector<vector<Edge>> Graph;
    vector<long long> distances;
    vector<int> prev;
    int nn;
    dijkstra(int n) : Graph(n), distances(n,1LL<<62), nn(n),prev(n,-1) {}

    bool add_edge(int from, int to, long long cost){
        Graph.at(from).push_back({to,cost});
        return true;
    }

    bool clear(){
        for(int i=0;i<nn;i++){
            distances.at(i) = 1LL << 62;
        }
        return true;
    }

    bool solve(int start){
        using Pair = pair<long long,int>;
        priority_queue<Pair,vector<Pair>,greater<Pair>> q;
        distances.at(start)=0;
        q.push({0, start});
        while(q.size()>0){
            long long dist = q.top().first;
            int from = q.top().second;
            q.pop();
            if(dist > distances.at(from))continue;
            for(auto & edge:Graph.at(from)){
                long long d=distances.at(from)+edge.cost;
                if(d < distances.at(edge.to)){
                    prev[edge.to]=from;
                    q.push({distances.at(edge.to) = d,edge.to});
                }
            }
        }
        return true;
    }

    long long get_dist(int i){
        if(distances[i]==1LL<<62){
            return  -1; 
        }else{
            return distances[i];
        }
    }
    vector<int> rest(int s,int g){
        vector<int> ans;
        int now=g;
        while(now!=-1){
            ans.push_back(now);
            now=prev[now];
        }
        reverse(ans.begin(),ans.end());
        return ans;
    }

};

int main(){
    int n,m,p;
    ll y;
    cin >> n >> m >> p >> y;
    dijkstra dij(n);
    for(int i=0;i<m;i++){
        int a,b;
        ll c;
        cin >> a >> b >> c;
        a--;b--;
        dij.add_edge(a,b,c);
        dij.add_edge(b,a,c);
    }
    dij.solve(0);
    ll ans=0;
    for(int i=0;i<p;i++){
        int d;
        ll e;
        cin >> d >> e;
        d--;
        if(dij.get_dist(d)==-1)continue;
        ans = max(ans,(y-dij.get_dist(d))/e);
    }
    cout << ans << endl;
    return 0;
}
0