AtCoder Regular Contest 025

Submission #2818462

Source codeソースコード

#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

Task問題 C - ウサギとカメ
User nameユーザ名 betrue12
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 100
Source lengthソースコード長 1548 Byte
File nameファイル名
Exec time実行時間 1005 ms
Memory usageメモリ使用量 512 KB

Test case

Set

Set name Score得点 / Max score Cases
Sample - subtask0_sample-01.txt,subtask0_sample-02.txt
All 100 / 100 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

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
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