Submission #1533719

---

Source Code Expand

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

#define OUT(x)  cerr << #x << " = " << x << endl;
#define all(x)  x.begin(), x.end()
#define mp      make_pair
#define pii     pair<int, int>
#define pll     pair<long long, long long>
#define ll      long long

struct edge {
        int to, cost;
        edge(int to, int cost) : to(to), cost(cost) { };
        bool operator > (const edge &r) const { return cost > r.cost; }
        bool operator < (const edge &r) const { return cost < r.cost; }
};

static const int INF = 0x3f3f3f3f;

vector<edge> g[101010];
int n;

void dijkstra(int start, vector<int> &dis) {
        priority_queue<edge, vector<edge>, greater<edge>> q;
        dis[start] = 0;
        q.push((edge){ start, 0 });
        while (!q.empty()) {
                edge e1 = q.top(); q.pop();
                for (auto e2 : g[e1.to]) {
                        if (dis[e2.to] > dis[e1.to] + e2.cost) {
                                dis[e2.to] = dis[e1.to] + e2.cost;
                                q.push((edge){ e2.to, dis[e2.to] });
                        }
                }
        }
}

int main() {
        int n, m;
        double r, t;
        cin >> n >> m >> r >> t;
        vector<int> d(n);
        for (int i = 0; i < m; i ++) {
                int a, b, c;
                cin >> a >> b >> c;
                a --, b --;
                g[a].push_back({b, c});
                g[b].push_back({a, c});
        }
        int ans = 0;
        for (int goal = 0; goal < n; goal ++) {
                vector<int> dis(n, INF);
                dijkstra(goal, dis);
                vector<int> sorted_dis = dis;
                sort(all(sorted_dis));
                for (int a = 0; a < n; a ++) {
                        if (a == goal) continue;
                        int dis_a = dis[a];
                        int dis_b = dis_a * t;
                        dis_b = (dis_b + r - 1) / r;
                        int res = lower_bound(all(sorted_dis), dis_b) - sorted_dis.begin();
                        ans += res - 1;
                }
        }
        cout << ans << endl;
        return 0;
}

Submission Info

Judge Result