Submission #2935203

---

Source Code Expand

#include<iostream>
#include <list>
#include<stack>
#include<queue>
#include <vector>
#include <set>
#include<algorithm>
#include<math.h>
#include<stdlib.h>
#include<string>
#include <functional>
#include<fstream>
#include<array>

#define FOR(k,m,n) for(int (k)=(m);(k)<(n);(k)++)
#define REP(i,n) FOR((i),0,(n))
#define ll long long
#define CLR(a) memset((a),0,sizeof(a))
#define SZ(x) (int((x).size()))
#define WAITING(str) int str;std::cin>>str;
#define DEBUGING(str) cout<<str<<endl
using namespace std;

const ll MOD = 1000000007;// 10^9+7
const ll INF = (1ll << 60);

using ld = long double;
struct Edge { ll to, cost; };
enum Kind { RABBIT, TURTLE};
struct Score {
	ld time;
	Kind kind;
	ll place;
	bool operator < (const Score& oth)const {
		if (time != oth.time)return time < oth.time;
		else if (kind != oth.kind)return kind < oth.kind;
		else return place < oth.place;
	}
	bool operator == (const Score& oth)const {
		return (time == oth.time)
			&& (kind == oth.kind)
			&& (place == oth.place);
	}
	bool operator > (const Score& oth)const {
		if (*this == oth)return false;
		if (*this < oth)return false;
		return true;
	}
};

constexpr ll MAX_N = 100000;


//変数
ll N, M, R, T;
array<vector<Edge>, MAX_N> edges;
vector<ll> d;

void dijkstra(ll s)
{
	using P = pair<ll, ll>;
	priority_queue<P, vector<P>, greater<P>> que;
	for (auto& num : d)num = INF;
	d[s] = 0;
	que.push(P(0, s));

	while (!que.empty())
	{
		P p = que.top(); que.pop();
		ll v = p.second;
		if (d[v] < p.first)continue;
		for (auto e : edges[v])
		{
			if (d[e.to] > d[v] + e.cost)
			{
				d[e.to] = d[v] + e.cost;
				que.push(P(d[e.to], e.to));
			}
		}
	}
}





//サブ関数
//入力
void input()
{
	cin >> N >> M >> R >> T;
	d.resize(N);
	REP(i, M)
	{
		ll a, b, c;
		cin >> a >> b >> c;
		a--; b--;
		edges[a].push_back({ b,c });
		edges[b].push_back({ a,c });
	}
}

priority_queue<Score, vector<Score>, greater<Score>> make_scores(ll goal)
{
	dijkstra(goal);
	priority_queue<Score, vector<Score>, greater<Score>> pq;

	REP(i, N)if (i != goal)
	{
		pq.push({ (ld)d[i] / R, RABBIT , i });
		pq.push({ (ld)d[i] / T, TURTLE , i });
	}
	return pq;
}

ll count_BC_combination(ll goal)
{
	ll res = 0;
	set<ll> turtleStart;
	auto pq = make_scores(goal);

	while (!pq.empty())
	{
		auto score = pq.top(); pq.pop();
		if (score.kind == TURTLE)
		{
			turtleStart.insert(score.place);
		}
		else {
			ll turtleWay = turtleStart.size();
			if (turtleStart.find(score.place) != turtleStart.end())turtleWay--;
			res += turtleWay;
		}
	}
	return res;
}

//計算
void calc()
{
	ll ans = 0;
	REP(i, N)ans += count_BC_combination(i);
	cout << ans << endl;
}


//デバッグ
void debug()
{
	int N;
	cin>>N;
}


//メイン関数
int main()
{
	input();
	calc();
	debug();
	
	return 0;
}

Submission Info

Judge Result