Submission #3712764

---

Source Code Expand

#include <bits/stdc++.h>
#define FOR(i, begin, end) for(int i=(begin);i<(end);i++)
#define REP(i, n) FOR(i,0,n)
#define IFOR(i, begin, end) for(int i=(end)-1;i>=(begin);i--)
#define IREP(i, n) IFOR(i,0,n)
#define SORT(a) sort(a.begin(), a.end())
#define REVERSE(a) reverse(a.begin(), a.end())
#define Lower_bound(v, x) distance(v.begin(), lower_bound(v.begin(), v.end(), x))
#define Upper_bound(v, x) distance(v.begin(), upper_bound(v.begin(), v.end(), x))
#define int long long
#define INF 1000000000000000000
using namespace std;

#define ANS(f) if(f) cout << "YES" << endl; else cout << "NO" << endl;

typedef vector<int> vec;
typedef vector<vec> mat;
typedef pair<int, int> Pii;

template<typename T>
void readv(vector<T> &a){ REP(i, a.size()) cin >> a[i]; }
void readi(vector<int> &a){ REP(i, a.size()){cin >> a[i]; a[i]--;} }
void debug(mat m){REP(i, m.size()){ REP(j, m[0].size()){ cout << m[i][j] << ","; } cout << endl; }}

struct edge{int to, cost;};

class Graph
{
public:
    int V;
    vector<vector<edge>> G;
    vec d;

    Graph(int V): V(V){
        G = vector<vector<edge>>(V, vector<edge>(0));
        d = vec(V);
    }

    void add_edge(int from, int to, int cost){
        G[from].push_back(edge({to, cost}));
    }

    void add_edge2(int v1, int v2, int cost){
        add_edge(v1, v2, cost);
        add_edge(v2, v1, cost);
    }

    void dijkstra(int s, int t){
        priority_queue<Pii, vector<Pii>, greater<Pii>> que;
        fill(d.begin(), d.end(), INF);
        d[s] = 0;
        que.push(Pii(0, s));

        while(!que.empty()){
            Pii p = que.top(); que.pop();
            int v = p.second;
            if(v == t) return;
            if(d[v] < p.first) continue;
            REP(i, G[v].size()){
                edge e = G[v][i];
                if(d[e.to] > d[v] + e.cost){
                    d[e.to] = d[v] + e.cost;
                    que.push(Pii(d[e.to], e.to));
                }
            }
        }
    }

};

signed main(){

    int N, M, R, T; cin >> N >> M >> R >> T;
    Graph G(N);
    vec a(M), b(M), c(M);
    REP(i, M){
        cin >> a[i] >> b[i] >> c[i];
        a[i]--; b[i]--;
        G.add_edge2(a[i], b[i], c[i]);
    }
    int ans = 0;
    REP(A, N){
        G.dijkstra(A, -1);
        SORT(G.d);
        FOR(B, 1, N){
            int D = (G.d[B] * T - 1) / R;
            if(D < G.d[B]) ans += Upper_bound(G.d, D) - 1;
            else ans += Upper_bound(G.d, D) - 2;
        }
    }
    cout << ans << endl;

    return 0;
}

Submission Info

Judge Result