Submission #2383632

---

Source Code Expand

#include <bits/stdc++.h>

int n, m, x, y;
std::vector<std::vector<std::pair<int, int>>> g;

std::vector<int> solve(int s){
	std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<std::pair<int, int>>> qu;
	std::vector<int> min_cost(n, 1e9); qu.push({0, s}); min_cost[s] = 0;
	
	while(!qu.empty()){
		auto p = qu.top(); qu.pop();
		
		for(auto e : g[p.second]){
			if(p.first + e.second >= min_cost[e.first]) continue;
			min_cost[e.first] = p.first + e.second;
			qu.push({min_cost[e.first], e.first});
		}
	}
	
	return min_cost;
}

int main(){
	std::cin >> n >> m >> x >> y; g.resize(n);
	for(int i = 0; i < m; i++){
		int a, b, c; std::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 i = 0; i < n; i++){
		std::vector<int> A, B;
		A = B = solve(i);
		
		for(int j = 0; j < n; j++) A[j] *= y;
		for(int j = 0; j < n; j++) B[j] *= x; sort(begin(B), end(B));
		
		for(int j = 0; j < n; j++){
			if(i == j) continue;
			int k = upper_bound(begin(B), end(B), A[j] - 1) - begin(B); k--;
			
			ans += k;
		}
	}
	
	std::cout << ans << std::endl;
	return 0;
}

Submission Info

Judge Result