Submission #3719683

---

Source Code Expand

#include "bits/stdc++.h"
using namespace std;
typedef unsigned long long ll;
const ll MOD = 1e9 + 7;
const double PI = 3.141592653589793238;
const double EPS = 1e-10;
typedef pair<ll, ll> P;
vector<P> G[2500];
ll dist[2500];
ll N, M, R, T;
void dijkstra(int v) {
	fill(dist, dist + N, 1LL << 60);
	dist[v] = 0;
	priority_queue<P, vector<P>, greater<P>> Q;
	Q.push(P(0, v));
	while (!Q.empty()) {
		P p = Q.top(); Q.pop();
		if (p.first > dist[p.second]) continue;
		for (P e : G[p.second]) {
			if (dist[e.first] > dist[p.second] + e.second) {
				dist[e.first] = dist[p.second] + e.second;
				Q.push(P(dist[e.first], e.first));
			}
		}
	}
}
int main() {
	cin >> N >> M >> R >> T;
	for (int i = 0; i < M; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		a--; b--;
		G[a].emplace_back(b, c);
		G[b].emplace_back(a, c);
	}
	ll ans = 0;
	for (int i = 0; i < N; i++) {
		dijkstra(i);
		vector<ll> vec;
		for (int j = 0; j < N; j++) {
			if (i == j) continue;
			vec.push_back(dist[j] * R);
		}
		sort(vec.begin(), vec.end());
		for (int j = 0; j < N; j++) {
			if (i == j) continue;
			ans += lower_bound(vec.begin(), vec.end(), dist[j] * T) - vec.begin();
		}
		if (T > R) {
			ans -= N - 1;
		}
	}
	cout << ans << endl;
}

Submission Info

Judge Result