Submission #1511410

---

Source Code Expand

#include<bits/stdc++.h>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) for(int i = 0; i < (b); i++)
#define all(a) (a).begin(), (a).end()
#define show(x)  cerr << #x << " = " << (x) << endl;
const int INF = 1e8;
using namespace std;

class Edge{
    public:
        int to, cost;
        Edge(int to, int cost) : to(to) ,cost(cost) {}
};

class Node{
    public:
        int dis;
        bool isUsed;
        Node(){
            this->dis = INF;
            this->isUsed = 0;
        }
        bool operator < ( const Node &right ) const {
            return dis < right.dis;
        }
};

typedef vector<vector<Edge>> AdjList;

int dijkstra(AdjList g, int start, int n, int r, int t){
    vector<Node> node(n);
    priority_queue<int, vector<pair<int, int>>, greater<pair<int, int>>> q;

    q.push(make_pair(0, start));
    node[start].dis = 0;

    pair<int, int> u;
    while(not q.empty()){
        u = q.top(); q.pop();
        int current = u.second;
        node[current].isUsed = 1;

        rep(i,g[current].size()){
            int next = g[current][i].to;
            if(node[next].isUsed == 0){
                if(node[next].dis > node[current].dis + g[current][i].cost){
                    node[next].dis = node[current].dis + g[current][i].cost;
                    q.push(make_pair(node[next].dis, next));
                }
            }
        }
    }
    sort(all(node));
    rep(i,n) node[i].dis *= t;

    int ans = 0;
    range(i,1,n){
        Node tmp;
        tmp.dis = node[i].dis / t * r;
        ans += node.end() - upper_bound(all(node), tmp);
    }
    return ans;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, m, r, t;
    cin >> n >> m >> r >> t;

    AdjList g(n);
    rep(i,m){
        int a, b, c;
        cin >> a >> b >> c;
        a--; b--;
        g[a].emplace_back(Edge{b,c});
        g[b].emplace_back(Edge{a,c});
    }

    int ans = 0;
    rep(i,n){
        ans += dijkstra(g,i,n,r,t);
    }
    cout << ans << endl;
}

Submission Info

Judge Result