Submission #1647558

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

#define fst(t) std::get<0>(t)
#define snd(t) std::get<1>(t)
#define thd(t) std::get<2>(t)
#define unless(p) if(!(p))
#define until(p) while(!(p))

using ll = long long;
using P = std::tuple<int,int>;

const int dx[8] = {-1, 1, 0, 0, -1, -1, 1, 1}, dy[8] = {0, 0, -1, 1, -1, 1, -1, 1};

int N, M, R, T;
int dist[3000];
vector<P> G[3000];

template <class T>
using priority_queue_with_greater = std::priority_queue<T, std::vector<T>, std::greater<T>>;

priority_queue_with_greater<P> pq;

template <typename T, typename U, int n>
void dijkstra(T s, std::vector<std::tuple<T, U>> (&graph)[n], U (&dist)[n], priority_queue_with_greater<std::tuple<U, T> > &pq){
    std::fill(dist, dist+n, std::numeric_limits<U>::max() / 2);
    dist[s] = 0;
    pq.emplace(dist[s], s);

    while(!pq.empty()){
        T u;
        U d;
        std::tie(d, u) = pq.top();
        pq.pop();

        if(dist[u] < d){continue;}

        for(const auto& p : graph[u]){
            T v;
            U c;
            std::tie(v, c) = p;
            if(dist[v] > d + c){
                dist[v] = d + c;
                pq.emplace(dist[v], v);
            }
        }
    }
}


int main(){
    std::cin.tie(nullptr);
    std::ios::sync_with_stdio(false);

    std::cin >> N >> M >> R >> T;

    for(int i=0;i<M;++i){
        int a, b, c;
        std::cin >> a >> b >> c;

        G[a].emplace_back(b, c);
        G[b].emplace_back(a, c);
    }
    
    ll res = 0ll;
    for(int i=1;i<=N;++i){
        dijkstra(i, G, dist, pq);

        sort(dist+1, dist+1+N);

        for(int j=2;j<=N;++j){
            double u = 1. * dist[j] * R / T;
            
            // if minimizing, lb satisfies lb > ub
            // if maximizing, lb satisfies lb < ub
            int64_t lb = 1, ub = N + 1;
            
            while(std::abs(ub - lb) > 1){
                int64_t mid = (lb + ub) / 2;

                if(u >= dist[mid]){
                    lb = mid;
                }else{
                    ub = mid;
                }
            }

            ll c = N - lb - (T > R ? 1 : 0);
            res += c;
        }
    }

    std::cout << res << std::endl;
}

Submission Info

Judge Result