Submission #1389922

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
const ull mod = 1e9 + 7;
const int INFINT = INT_MAX/2;
#define REP(i,n) for(int i=0;i<(int)n;++i)

struct Edge{
    int dst;
    int weight;
    Edge(int dst, int weight): dst(dst), weight(weight) {}
};

struct TmpDist{
    int vertex;
    int dist;
    TmpDist(int vertex, int dist): vertex(vertex), dist(dist) {}
    bool operator< (const TmpDist& right)const{
        return dist > right.dist;
    }
};

typedef vector<Edge> Edges;
typedef vector<Edges> Graph;

vector<int> dijkstra(Graph &G, int r){
    int V = G.size();
    vector<int> dist(V, INFINT);
    priority_queue<TmpDist> pq;
    vector<bool> check(V, false);
    TmpDist init(r, 0);
    pq.push(init);
    while(!pq.empty()){
        TmpDist td = pq.top();pq.pop();
        int now = td.vertex;
        if(!check[now]){
            check[now] = true;
            dist[now] = td.dist;
            for (int i=0;i<G[now].size();i++){
                if(dist[G[now][i].dst] > td.dist + G[now][i].weight){
                    TmpDist tdCandidate(G[now][i].dst, td.dist + G[now][i].weight);
                    pq.push(tdCandidate);
                }
            }
        }
    }
    return dist;
}

int main(){
    int N, M, R, T;
    cin >> N >> M >> R >> T;
    Graph G(N);
    REP(i, M){
        int a, b, c;
        cin >> a >> b >> c;
        a--;b--;
        Edge e1(b, c), e2(a, c);
        G[a].push_back(e1);
        G[b].push_back(e2);
    }
    int res = 0;
    REP(i, N){
        vector<int> dist = dijkstra(G, i);
        sort(dist.begin(), dist.end());
        vector<int> dist1(N), dist2(N);
        REP(j, N){
            dist1[j] = T*dist[j];
            dist2[j] = R*dist[j];
        }
        for(int j=1;j<N;j++){
            res += lower_bound(dist2.begin(), dist2.end(), dist1[j]) - dist2.begin()-1;
        }
    }
    cout << res << endl;
    return 0;
}

Submission Info

Judge Result