Submission #2818462


Source Code Expand

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

struct edge { long long to, cost;};
typedef pair<long long, long long> Pair;

vector<long long> dijkstra(long long s, long long n, const vector<edge> G[]){
    vector<long long> dist = {};
    long long INF = 1LL<<60;
    dist.resize(n);
    for(int i=0; i<n; i++){
        dist[i] = INF;
    }
    priority_queue<Pair, vector<Pair>, greater<Pair>> que;
    dist[s] = 0;
    que.push(Pair(0, s));
    while(!que.empty()){
        Pair p = que.top();
        que.pop();
        long long v = p.second;
        if(dist[v] < p.first)continue;
        for(int i=0;i<G[v].size(); i++){
            edge e = G[v][i];
            if(dist[e.to] > dist[v] + e.cost){
                dist[e.to] = dist[v] + e.cost;
                que.push(Pair(dist[e.to], e.to));
            }
        }
    }
    return dist;
}

int main(){
    long long i, j, k;
    long long N, M, R, T;
    vector<edge> edges[2500];
    cin >> N >> M >> R >> T;
    for(i=0; i<M; i++){
        long long a, b, c;
        cin >> a >> b >> c;
        edges[a-1].push_back({b-1, c});
        edges[b-1].push_back({a-1, c});
    }
    long long ans = 0;
    for(i=0; i<N; i++){
        vector<long long> dist = dijkstra(i, N, edges);
        sort(dist.begin(), dist.end());
        long long t = 0;
        for(long long r=1; r<N; r++){
            while(t<N-1 && R*dist[t+1] < T*dist[r]) t++;
            ans += (t>=r) ? t-1 : t;
        }
    }
    cout << ans << endl;
    return 0;
}

Submission Info

Submission Time
Task C - ウサギとカメ
User betrue12
Language C++14 (GCC 5.4.1)
Score 100
Code Size 1548 Byte
Status AC
Exec Time 1005 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 6 ms 256 KB
subtask1_06.txt AC 8 ms 384 KB
subtask1_07.txt AC 28 ms 512 KB
subtask1_08.txt AC 35 ms 384 KB
subtask1_09.txt AC 298 ms 512 KB
subtask1_10.txt AC 275 ms 384 KB
subtask1_11.txt AC 124 ms 384 KB
subtask1_12.txt AC 889 ms 512 KB
subtask1_13.txt AC 885 ms 512 KB
subtask1_14.txt AC 986 ms 512 KB
subtask1_15.txt AC 680 ms 512 KB
subtask1_16.txt AC 1005 ms 512 KB