Submission #184204

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

const int N = 2525;
int n,m,r,t;
struct edge{int to,cost;};
vector<edge> G[N];


typedef pair<int,int> P;
int d[N], e[N];

int dijkstra(int s){
    fill(d,d+n,INT_MAX/2);

    priority_queue<P,vector<P>,greater<P>> pq;
    pq.push({0,s});
    d[s] = 0;
    while(!pq.empty()){
        int v = pq.top().second;
        int l = pq.top().first;
        pq.pop();

        if(d[v] < l) continue;
        for(edge &e : G[v]){
            int w = e.to;
            int c = e.cost;
            if(d[w] > d[v] + c){
                d[w] = d[v] + c;
                pq.push({d[w],w});
            }
        }
    }

    sort(d,d+n);
    for(int i = 0; i < n; i++){
        e[i] = d[i] * t;
        d[i] *= r;
        assert(e[i] >= 0 && d[i] >= 0);
    }

    int res = 0;

    if(n <= 600){
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                if(i == j || i == 0 || j == 0) continue;
                res += d[i]*t > d[j]*r;
            }
        }
    } else {
        for(int i = 1; i < n; i++){
            res += lower_bound(d, d+n, e[i]) - d - 1;
            if(r < t) res--;
        }
    }
    return res;
}

int main(){
    cin >> n >> m >> r >> t;
    for(int i = 0; i < m; i++){
        int a,b,c;
        cin >> a >> b >> c;
        G[a-1].push_back({b-1,c});
        G[b-1].push_back({a-1,c});
    }

    long long ans = 0;
    for(int a = 0; a < n; a++){
        ans += dijkstra(a);
    }
    cout << ans << endl;
    return 0;
}

Submission Info

Judge Result