Submission #1481447


Source Code Expand

#include<bits/stdc++.h>

using namespace std;

const int INF = 1 << 29;

typedef pair< int, int > Pi;
struct edge
{
  int to, cost;
};
typedef vector< vector< edge > > Graph;

int Dijkstra(Graph &graph, int s, int g, vector< int > &min_cost)
{
  min_cost.assign(graph.size(), INF);
  priority_queue< Pi, vector< Pi >, greater<> > que;
  que.push(make_pair(0, s));
  min_cost[s] = 0;
  while(!que.empty()) {
    int now = que.top().second;
    int cost = que.top().first;
    que.pop();
    if(now == g) return (cost);
    if(cost > min_cost[now]) continue;
    for(int i = 0; i < graph[now].size(); i++) {
      edge &e = graph[now][i];
      if(cost + e.cost < min_cost[e.to]) {
        min_cost[e.to] = cost + e.cost;
        que.emplace(min_cost[e.to], e.to);
      }
    }
  }
  return (-1);
}

int main()
{
  int N, M, R, T;

  cin >> N >> M >> R >> T;

  Graph g(N);
  for(int i = 0; i < M; i++) {
    int A, B, C;
    cin >> A >> B >> C;
    --A, --B;
    g[A].push_back((edge) {B, C});
    g[B].push_back((edge) {A, C});
  }

  int ret = 0;
  for(int C = 0; C < N; C++) {
    vector< int > st;
    Dijkstra(g, C, -1, st);
    sort(begin(st), end(st));
    int tail = 1;
    for(int i = 1; i < st.size(); i++) {
      while(tail < st.size() && 1LL * st[tail] * T <= 1LL * st[i] * R) ++tail;
      ret += st.size() - tail;
      if(tail <= i) --ret;
    }
  }

  cout << ret << endl;
}

Submission Info

Submission Time
Task C - ウサギとカメ
User ei13333
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1456 Byte
Status WA
Exec Time 994 ms
Memory 384 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 100
Status
AC × 2
AC × 14
WA × 4
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 256 KB
subtask0_sample-02.txt AC 1 ms 256 KB
subtask1_01.txt AC 1 ms 256 KB
subtask1_02.txt AC 1 ms 256 KB
subtask1_03.txt AC 1 ms 256 KB
subtask1_04.txt AC 1 ms 256 KB
subtask1_05.txt AC 6 ms 256 KB
subtask1_06.txt AC 8 ms 256 KB
subtask1_07.txt AC 29 ms 384 KB
subtask1_08.txt AC 36 ms 256 KB
subtask1_09.txt AC 300 ms 384 KB
subtask1_10.txt AC 279 ms 384 KB
subtask1_11.txt AC 126 ms 384 KB
subtask1_12.txt WA 894 ms 384 KB
subtask1_13.txt WA 888 ms 384 KB
subtask1_14.txt WA 987 ms 384 KB
subtask1_15.txt AC 675 ms 384 KB
subtask1_16.txt WA 994 ms 384 KB