Submission #1441133


Source Code Expand

#include <bits/stdc++.h>
#define repeat(i, n) for( int i = 0; (i) < (n); ++(i) )
#define repeat_to(i, n) for( int i = 0; (i) <= (n); ++(i) )
#define repeat_from(i, m, n) for( int i = (m); (i) < (n); ++(i) )
#define repeat_from_to(i, m, n) for( int i = (m); (i) <= (n); ++(i) )
#define repeat_from_reverse(i, m, n) for( int i = (n) - 1; (i) >= (m); --(i) )
#define dump(x) cout << " " << #x << "=" << x
#define vdump(v) for(size_t t=0; t<v.size(); ++t){cout << " " << #v << "[" << t << "]=" << v[t];} cout << endl
using namespace std;
using lint = long long;

/****************** グラフ ******************/
// 諸宣言
using Weight = int;
using Flow = int;
struct Edge {
    int src, dst;
    Weight weight;
    Flow cap;
    Edge() : src(0), dst(0), weight(0) {}
    Edge(int s, int d, Weight w) : src(s), dst(d), weight(w) {}
};
using Edges = std::vector<Edge>;
using Graph = std::vector<Edges>;
using Array = std::vector<Weight>;
using Matrix = std::vector<Array>;

void add_edge(Graph &g, int a, int b, Weight w = 1) {
    g[a].emplace_back(a, b, w);
    g[b].emplace_back(b, a, w);
}
void add_arc(Graph &g, int a, int b, Weight w = 1) { g[a].emplace_back(a, b, w); }

// ダイクストラ法(プライオリティーキュー)O((E+V)logV)
std::vector<Weight> dijkstra(const Graph &g, int s) {
    const Weight INF = std::numeric_limits<Weight>::max() / 8;
    using state = std::tuple<Weight, int>;
    std::priority_queue<state> q;
    std::vector<Weight> dist(g.size(), INF);
    dist[s] = 0;
    q.emplace(0, s);
    while (q.size()) {
        Weight d;
        int v;
        std::tie(d, v) = q.top();
        q.pop();
        d *= -1;
        /* if(v == t) return d; */
        if (dist[v] < d) continue;
        for (auto &e : g[v]) {
            if (dist[e.dst] > dist[v] + e.weight) {
                dist[e.dst] = dist[v] + e.weight;
                q.emplace(-dist[e.dst], e.dst);
            }
        }
    }
    return dist;
}

int main(void) {
    int n, m;
    double r, t;
    cin >> n >> m >> r >> t;
    Graph g(n);
    repeat(i, m) {
        int a, b, c;
        cin >> a >> b >> c;
        --a; --b;
        add_edge(g, a, b, c);
    }
    
    int ans = 0;
    repeat(i, n) {
        vector<Weight> res = dijkstra(g, i);
        vector<double> rab(n), tur(n);
        repeat(j, n) {
            rab[j] = res[j] / r;
            tur[j] = res[j] / t;
        }
        sort(rab.begin(), rab.end());
        //dump(r); dump(t); cout << endl; vdump(res); vdump(rab); vdump(tur);
        repeat(j, n) {
            if(i == j) continue;
            auto ub = upper_bound(rab.begin(), rab.end(), tur[j]);
            auto d = distance(ub, rab.end());
            ans += d;
            if(r < t && d > 0) --ans;
            //dump(i); dump(j); cout << " " << distance(ub, rab.end()) << endl;
        }
    }
    cout << ans << endl;
    return 0;
}

Submission Info

Submission Time
Task C - ウサギとカメ
User maphylageo
Language C++14 (GCC 5.4.1)
Score 0
Code Size 2966 Byte
Status WA
Exec Time 1370 ms
Memory 512 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 100
Status
AC × 2
AC × 14
WA × 4
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 30 ms 384 KB
subtask1_08.txt AC 39 ms 384 KB
subtask1_09.txt AC 336 ms 384 KB
subtask1_10.txt AC 334 ms 384 KB
subtask1_11.txt AC 137 ms 384 KB
subtask1_12.txt WA 1312 ms 512 KB
subtask1_13.txt WA 1317 ms 512 KB
subtask1_14.txt WA 1326 ms 512 KB
subtask1_15.txt AC 778 ms 512 KB
subtask1_16.txt WA 1370 ms 512 KB