Submission #1515441


Source Code Expand

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

using ll = long long;
using weight = double;

constexpr weight INF = 1e9;

struct edge {
    int from, to;
    weight cost;

    bool operator<(edge const& rhs) const {
        return cost > rhs.cost;
    }
};

using edges = std::vector<edge>;
using graph = std::vector<edges>;

void add_edge(graph& g, int from, int to, weight cost) {
    g[from].push_back(edge{from, to, cost});
}

std::vector<weight> dijkstra(graph& g, int s) {
    using P = std::pair<weight, int>;
    std::vector<weight> d(g.size(), INF);
    std::priority_queue<P, std::vector<P>, std::greater<P>> que;
    fill(d.begin(), d.end(), INF);
    d[s] = 0;
    que.push(P{0, s});

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


int main() {
    int N, M;
    double R, T;
    cin >> N >> M >> R >> T;
    graph g(N);
    for(int i = 0; i < M; ++i) {
        int a, b, c;
        cin >> a >> b >> c;
        a--; b--;
        add_edge(g, a, b, c);
        add_edge(g, b, a, c);
    }

    ll res = 0;
    for(int i = 0; i < N; ++i) {
        auto d = dijkstra(g, i);
        sort(d.begin(), d.end());
        for(int j = 1; j < N; ++j) {
            auto t = upper_bound(d.begin(), d.end(), d[j] * R / T) - d.begin();
            res += N - t - (t <= j);
        }
    }
    cout << res << endl;
}

Submission Info

Submission Time
Task C - ウサギとカメ
User Suibaka
Language C++14 (GCC 5.4.1)
Score 100
Code Size 1737 Byte
Status AC
Exec Time 1171 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 7 ms 256 KB
subtask1_06.txt AC 9 ms 256 KB
subtask1_07.txt AC 31 ms 384 KB
subtask1_08.txt AC 39 ms 384 KB
subtask1_09.txt AC 351 ms 384 KB
subtask1_10.txt AC 335 ms 384 KB
subtask1_11.txt AC 144 ms 384 KB
subtask1_12.txt AC 1073 ms 512 KB
subtask1_13.txt AC 1070 ms 512 KB
subtask1_14.txt AC 1167 ms 512 KB
subtask1_15.txt AC 798 ms 512 KB
subtask1_16.txt AC 1171 ms 512 KB