Submission #2935275

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
using lint = long long;
template<class T = int> using V  = vector<T>;
template<class T = int> using VV = V< V<T> >;
using P = pair<int, int>;

int main() {
  cin.tie(NULL); ios::sync_with_stdio(false);
  int n, m, r, t; cin >> n >> m >> r >> t;
  struct edge { int to, w; }; VV<edge> g(n);
  for (int i = 0; i < m; i++) {
    int a, b, c; cin >> a >> b >> c, a--, b--;
    g[a].push_back(edge{b, c});
    g[b].push_back(edge{a, c});
  }
  lint res = 0;
  for (int i = 0; i < n; i++) {
    priority_queue<P, V<P>, greater<P> > q; V<> d(n, 1e9);
    d[i] = 0; q.emplace(0, i);
    while (not q.empty()) {
      P p = q.top(); q.pop();
      int v = p.second;
      if (p.first > d[v]) continue;
      for (auto&& e : g[v]) {
        if (d[e.to] < d[v] + e.w) continue;
        d[e.to] = d[v] + e.w; q.emplace(d[e.to], e.to);
      }
    }
    sort(d.begin(), d.end());
    for (int j = 0; j < n; j++) {
      if (d[j] == 0) continue;
      res += d.end() - upper_bound(d.begin(), d.end(), d[j] * r / t);
    }
  }
  if (t > r) res -= n * (n - 1);
  cout << res << '\n';
}

Submission Info

Judge Result