Submission #2336825


Source Code Expand

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#include <cmath>
using namespace std;
using i64 = long long;
using P = pair<i64,i64>;
#define rep(i,s,e) for(int (i) = (s);i <= (e);(i)++)

i64 N,M;

i64 R,T;

struct edge{
  int to;
  i64 cost;
};

vector<vector<edge>> edges(3000);

i64 solve(int s){

  vector<i64> dist(N,1e18);

  {
    priority_queue<P,vector<P>,greater<P>> que;
    dist[s] = 0;
    que.emplace(dist[s],s);

    while(!que.empty()){
      int v = que.top().second;
      i64 d = que.top().first;
      que.pop();

      if(dist[v] < d) continue;

      for(auto & e : edges[v]){
        if(dist[e.to] > d + e.cost){
          dist[e.to] = d + e.cost;
          que.emplace(dist[e.to] , e.to);
        }
      }
    }
  }

  sort(begin(dist),end(dist));

  i64 res = 0;

  rep(i,1,N - 1){
    i64 ite = upper_bound(begin(dist),end(dist),dist[i] * R / T) - begin(dist);
    res += N - ite;
    if(ite <= i) res--;
  }

  return res;
}

int main(){
  cin >> N >> M >> R >> T;
  rep(i,0,M - 1){
    int a,b;
    i64 c;
    cin >> a >> b >> c;
    a--;
    b--;
    edges[a].push_back({b,c});
    edges[b].push_back({a,c});
  }

  i64 res = 0;

  rep(i,0,N - 1){
    res += solve(i);
  }

  cout << res << endl;
}

Submission Info

Submission Time
Task C - ウサギとカメ
User niuez
Language C++14 (GCC 5.4.1)
Score 100
Code Size 1387 Byte
Status AC
Exec Time 1125 ms
Memory 512 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 100 / 100
Status
AC × 2
AC × 18
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 384 KB
subtask1_06.txt AC 8 ms 384 KB
subtask1_07.txt AC 29 ms 512 KB
subtask1_08.txt AC 37 ms 384 KB
subtask1_09.txt AC 330 ms 512 KB
subtask1_10.txt AC 318 ms 384 KB
subtask1_11.txt AC 136 ms 512 KB
subtask1_12.txt AC 1032 ms 512 KB
subtask1_13.txt AC 1021 ms 512 KB
subtask1_14.txt AC 1120 ms 512 KB
subtask1_15.txt AC 755 ms 512 KB
subtask1_16.txt AC 1125 ms 512 KB