Submission #3719863
Source Code Expand
#include <bits/stdc++.h>
#define int long long
#define uint unsigned int
#define rep(i, a, n) for (int i = a; i < n; i++)
#define all(a) (a).begin(), (a).end()
#define sz(a) (a).size()
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define mt make_tuple
#define dump(x) cerr << #x << " = " << (x) << endl;
#define dumpi(i, x) cerr << string((i), ' ') << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
using namespace std;
using pii = pair<int, int>;
constexpr int MOD = 1000000007;
constexpr int INF = 1LL << 30;
constexpr double EPS = 1e-10;
template<class T> inline bool chmin(T &a, T b) { if (a > b) { a = b; return 1; } return 0; }
struct edge {
int to, cost;
edge() {}
edge(int t, int c): to(t), cost(c) {}
};
int N, M, R, T;
vector<edge> G[2510];
int dis[2510];
void dijkstra(int s) {
fill_n((int*)dis, 2510, INF);
dis[s] = 0;
priority_queue<pii, vector<pii>, greater<pii>> que;
que.push({0, s});
while (!que.empty()) {
int d, v;
tie(d, v) = que.top(); que.pop();
if (d < dis[v]) continue;
for (edge e : G[v]) {
if (chmin(dis[e.to], dis[v] + e.cost)) {
que.push({dis[e.to], e.to});
}
}
}
}
signed main() {
cin.tie(0);
ios_base::sync_with_stdio(false);
cout << fixed << setprecision(10);
cin >> N >> M >> R >> T;
rep(i, 0, M) {
int a, b, c;
cin >> a >> b >> c;
a--; b--;
G[a].eb(b, c);
G[b].eb(a, c);
}
int ans = 0;
rep(i, 0, N) {
dijkstra(i);
vector<double> v;
rep(j, 0, N) v.eb((double)dis[j]/T);
sort(all(v));
rep(j, 0, N) {
if (j == i) continue;
double rv = (double)dis[j]/R;
ans += (lower_bound(all(v), rv-EPS) - v.begin()) - 1;
}
}
cout << ans << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
C - ウサギとカメ |
User |
legosuke |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
1902 Byte |
Status |
WA |
Exec Time |
1388 ms |
Memory |
512 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
0 / 100 |
Status |
|
|
Set Name |
Test Cases |
Sample |
subtask0_sample-01.txt, subtask0_sample-02.txt |
All |
subtask0_sample-01.txt, subtask0_sample-02.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt |
Case Name |
Status |
Exec Time |
Memory |
subtask0_sample-01.txt |
AC |
1 ms |
384 KB |
subtask0_sample-02.txt |
AC |
1 ms |
384 KB |
subtask1_01.txt |
AC |
2 ms |
384 KB |
subtask1_02.txt |
AC |
2 ms |
384 KB |
subtask1_03.txt |
AC |
2 ms |
384 KB |
subtask1_04.txt |
AC |
1 ms |
384 KB |
subtask1_05.txt |
AC |
7 ms |
384 KB |
subtask1_06.txt |
WA |
10 ms |
384 KB |
subtask1_07.txt |
AC |
33 ms |
512 KB |
subtask1_08.txt |
WA |
39 ms |
384 KB |
subtask1_09.txt |
AC |
337 ms |
512 KB |
subtask1_10.txt |
AC |
347 ms |
384 KB |
subtask1_11.txt |
AC |
143 ms |
512 KB |
subtask1_12.txt |
WA |
1318 ms |
512 KB |
subtask1_13.txt |
AC |
1321 ms |
512 KB |
subtask1_14.txt |
AC |
1322 ms |
512 KB |
subtask1_15.txt |
AC |
789 ms |
512 KB |
subtask1_16.txt |
AC |
1388 ms |
512 KB |