Submission #183615

---

Source Code Expand

#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <fstream>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <sys/time.h>
#include <unordered_map>
#include <unordered_set>
#include <unistd.h>
#include <utility>
#include <vector>
using namespace std;
#define i64         int64_t
#define rep(i, n)   for(i64 i = 0; i < ((i64)(n)); ++i)
#define sz(v)       ((i64)((v).size()))
#define bit(n)      (((i64)1)<<((i64)(n)))
#define all(v)      (v).begin(), (v).end()

template <int POS, class TUPLE> void deploy(std::ostream &os, const TUPLE &tuple){}
template <int POS, class TUPLE, class H, class ...Ts> void deploy(std::ostream &os, const TUPLE &t){ os << (POS == 0 ? "" : ", ") << get<POS>(t); deploy<POS + 1, TUPLE, Ts...>(os, t); }
template <class ...Ts> std::ostream& operator<<(std::ostream &os, const std::tuple<Ts...> &t){ os << "("; deploy<0, std::tuple<Ts...>, Ts...>(os, t); os << ")"; return os; }
template <class T> std::ostream& operator<<(std::ostream &os, std::vector<T> &v){ int remain = v.size(); os << "{"; for(auto e: v) os << e << (--remain == 0 ? "" : ", "); os << "}"; return os; }
template <class T> std::ostream& operator<<(std::ostream &os, std::set<T> &v){ int remain = v.size(); os << "{"; for(auto e: v) os << e << (--remain == 0 ? "" : ", "); os << "}"; return os; }
template <class T> std::ostream& operator<<(std::ostream &os, std::queue<T> &q){ auto qq = q; os << "{"; for(; !qq.empty(); qq.pop()){ os << qq.front() << (qq.size() != 1 ? ", " : ""); } os << "}"; return os; }
template <class T> std::ostream& operator<<(std::ostream &os, std::priority_queue<T> &q){ auto qq = q; os << "{"; for(; !qq.empty(); qq.pop()){ os << qq.top() << (qq.size() != 1 ? ", " : ""); } os << "}"; return os; }
template <class T, class K> std::ostream& operator<<(std::ostream &os, std::pair<T, K> &p){ os << "(" << p.first << ", " << p.second << ")"; return os; }
template <class T, class K> std::ostream& operator<<(std::ostream &os, std::map<T, K> &mp){ int remain = mp.size(); os << "{"; for(auto e: mp) os << "(" << e.first << " -> " << e.second << ")" << (--remain == 0 ? "" : ", "); os << "}"; return os; }
template <class T, class K> std::ostream& operator<<(std::ostream &os, std::unordered_map<T, K> &mp){ int remain = mp.size(); os << "{"; for(auto e: mp) os << "(" << e.first << " -> " << e.second << ")" << (--remain == 0 ? "" : ", "); os << "}"; return os; }
#define DEBUG0() { char buf[100]; sprintf(buf, "line:%3d | ", __LINE__); std::cout << buf << std::endl; }
#define DEBUG1(var0) { char buf[100]; sprintf(buf, "line:%3d | ", __LINE__); std::cout << buf << (#var0) << "=" << (var0) << std::endl; }
#define DEBUG2(var0, var1) { char buf[100]; sprintf(buf, "line:%3d | ", __LINE__); std::cout << buf << (#var0) << "=" << (var0) << ", " << (#var1) << "=" << (var1) << std::endl; }
#define DEBUG3(var0, var1, var2) { char buf[100]; sprintf(buf, "line:%3d | ", __LINE__); std::cout << buf << (#var0) << "=" << (var0) << ", " << (#var1) << "=" << (var1) << ", " << (#var2) << "=" << (var2) << std::endl; }
#define DEBUG4(var0, var1, var2, var3) { char buf[100]; sprintf(buf, "line:%3d | ", __LINE__); std::cout << buf << (#var0) << "=" << (var0) << ", " << (#var1) << "=" << (var1) << ", " << (#var2) << "=" << (var2) << ", " << (#var3) << "=" << (var3) << std::endl; }
#define DEBUG5(var0, var1, var2, var3, var4) { char buf[100]; sprintf(buf, "line:%3d | ", __LINE__); std::cout << buf << (#var0) << "=" << (var0) << ", " << (#var1) << "=" << (var1) << ", " << (#var2) << "=" << (var2) << ", " << (#var3) << "=" << (var3) << ", " << (#var4) << "=" << (var4) << std::endl; }
#define DEBUG6(var0, var1, var2, var3, var4, var5) { char buf[100]; sprintf(buf, "line:%3d | ", __LINE__); std::cout << buf << (#var0) << "=" << (var0) << ", " << (#var1) << "=" << (var1) << ", " << (#var2) << "=" << (var2) << ", " << (#var3) << "=" << (var3) << ", " << (#var4) << "=" << (var4) << ", " << (#var5) << "=" << (var5) << std::endl; }
#define ASSERT(f) { if(!(f)){ DEBUG1("error"); while(true); }}



template <typename T> class Dijkstra
{
public:
  void addEdge(int from, int dest, T cost);
  void update(int source);
  T getDistance(int vertex);
  
  ~Dijkstra();
  Dijkstra(int vertex_num);
  
private:
  const int vertex_num;
  T *distances;
  
  class Edge
  {
  public:
    int target;
    T distance;
    Edge(int target, T distance) : target(target), distance(distance) {}
  };
  std::vector<Edge> *edges;
  
  class QueueElement
  {
  public:
    T distance;
    int vertex;
    inline QueueElement(T distance, int vertex) : distance(distance), vertex(vertex){}
    inline bool operator>(const QueueElement &e)const{ return distance > e.distance; }
  };
};

template <typename T>
inline Dijkstra<T>::~Dijkstra()
{
  delete [] edges;
  delete [] distances;
}

template <typename T>
inline Dijkstra<T>::Dijkstra(int vertex_num) : vertex_num(vertex_num)
{
  edges = new vector<Edge>[vertex_num];
  distances = new T[vertex_num];
}

template <typename T>
inline T Dijkstra<T>::getDistance(int vertex)
{
  return distances[vertex];
}

template <typename T>
inline void Dijkstra<T>::update(int source)
{
  memset(distances, -1, sizeof(T) * vertex_num);

  priority_queue<QueueElement, vector<QueueElement>, greater<QueueElement> > q;
  distances[source] = 0;
  q.push(QueueElement(0, source));
  
  for(int total_size = 1; 0 < total_size; q.pop()){
    int vertex = q.top().vertex;
    T distance = q.top().distance;
    if(distances[vertex] < distance) continue;
    --total_size;
    
    for(auto e : edges[vertex]){
      int next_vertex = e.target;
      T next_distance = e.distance + distance;
      if(distances[next_vertex] == -1){
        ++total_size;
        distances[next_vertex] = next_distance;
        q.push(QueueElement(next_distance, next_vertex));
      }else if(next_distance < distances[next_vertex]){
        distances[next_vertex] = next_distance;
        q.push(QueueElement(next_distance, next_vertex));
      }
    }
  }
}

template <typename T>
inline void Dijkstra<T>::addEdge(int from, int dest, T cost)
{
  edges[from].push_back(Edge(dest, cost));
}



int main()
{
  i64 n, m, r, t;
  cin >> n >> m >> r >> t;
  
  Dijkstra<i64> dijkstra(n);
  rep(i, m){
    i64 a, b, c;
    cin >> a >> b >> c; --a, --b;
    dijkstra.addEdge(a, b, c);
    dijkstra.addEdge(b, a, c);
  }
  
  i64 total = 0;
  rep(target, n){
    dijkstra.update(target);
    vector<i64> a;
    rep(i, n)if(target != i) a.push_back(dijkstra.getDistance(i));
    sort(all(a));
    i64 cur = 0;
    rep(i, sz(a)){
      while(cur < sz(a) && a[cur] * t <= a[i] * r) ++cur;
      total += sz(a) - cur - (cur <= i ? 1 : 0);
    }
  }
  cout << total << endl;
   
}

Submission Info

Judge Result