Submission #2935123

---

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 int INF = (1 << 30);

struct Edge { int to, cost; };
enum Kind { RABBIT, TURTLE };
using Score = pair<double, Kind>;
using P = pair<int, int>;
constexpr int MAX_N = 100000;


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

void dijkstra(int s)
{
	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();
		int 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)
	{
		int 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(int goal)
{
	dijkstra(goal);
	priority_queue<Score, vector<Score>, greater<Score>> pq;

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

int count_BC_combination(int goal)
{
	int res = 0;
	int turtleWay = 0;
	auto pq = make_scores(goal);

	while (!pq.empty())
	{
		auto score = pq.top(); pq.pop();
		if (score.second == TURTLE)
		{
			turtleWay++;
		}
		else {
			res += turtleWay;
		}
	}
	return res;
}

//計算
void calc()
{
	int 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