Submission #3719840


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) - 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 1898 Byte
Status WA
Exec Time 1370 ms
Memory 512 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 100
Status
AC × 2
AC × 15
WA × 3
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 1 ms 384 KB
subtask1_02.txt AC 1 ms 384 KB
subtask1_03.txt AC 1 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 345 ms 384 KB
subtask1_11.txt AC 142 ms 512 KB
subtask1_12.txt WA 1312 ms 512 KB
subtask1_13.txt AC 1306 ms 512 KB
subtask1_14.txt AC 1321 ms 512 KB
subtask1_15.txt AC 788 ms 512 KB
subtask1_16.txt AC 1370 ms 512 KB