Submission #185441


Source Code Expand

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

int d[2500];
vector <pair<int, int> > v[2500];

int main()
{
    int n, m, r, t, i, j;
    long long ans = 0;
    
    scanf("%d %d %d %d", &n, &m, &r, &t);
    
    for (i = 0; i < m; i++) {
        int x, y, z;
        
        scanf("%d %d %d", &x, &y, &z);
        
        x--;
        y--;
        
        v[x].push_back(make_pair(y, z));
        v[y].push_back(make_pair(x, z));
    }
    
    for (i = 0; i < n; i++) {
        vector <int> w;
        priority_queue <pair<int, int> > q;
        
        for (j = 0; j < n; j++) d[j] = 1e9;
        
        d[i] = 0;
        q.push(make_pair(0, i));
        
        while (!q.empty()) {
            int x = -q.top().first;
            int y = q.top().second;
            
            q.pop();
            
            if (d[y] != x) continue;
            
            for (j = 0; j < v[y].size(); j++) {
                if (d[v[y][j].first] > x + v[y][j].second) {
                    d[v[y][j].first] = x + v[y][j].second;
                    q.push(make_pair(-d[v[y][j].first], v[y][j].first));
                }
            }
        }
        
        for (j = 0; j < n; j++) {
            if (i != j) w.push_back(d[j]);
        }
        
        sort(w.begin(), w.end());
        
        for (j = 0; j < w.size(); j++) {
            int x = upper_bound(w.begin(), w.end(), w[j] * r / t) - w.begin();
            
            if (x <= j) {
                ans += w.size() - x - 1;
            } else {
                ans += w.size() - x;
            }
        }
    }
    
    printf("%lld\n", ans);
    
    return 0;
}

Submission Info

Submission Time
Task C - ウサギとカメ
User kawatea
Language C++ (G++ 4.6.4)
Score 100
Code Size 1760 Byte
Status AC
Exec Time 1565 ms
Memory 1052 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:16:41: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
./Main.cpp:21:38: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]

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 20 ms 920 KB
subtask0_sample-02.txt AC 19 ms 912 KB
subtask1_01.txt AC 21 ms 916 KB
subtask1_02.txt AC 23 ms 920 KB
subtask1_03.txt AC 21 ms 920 KB
subtask1_04.txt AC 21 ms 936 KB
subtask1_05.txt AC 28 ms 920 KB
subtask1_06.txt AC 31 ms 920 KB
subtask1_07.txt AC 60 ms 1052 KB
subtask1_08.txt AC 70 ms 844 KB
subtask1_09.txt AC 480 ms 1048 KB
subtask1_10.txt AC 460 ms 920 KB
subtask1_11.txt AC 208 ms 936 KB
subtask1_12.txt AC 1450 ms 956 KB
subtask1_13.txt AC 1423 ms 932 KB
subtask1_14.txt AC 1565 ms 1048 KB
subtask1_15.txt AC 1059 ms 1044 KB
subtask1_16.txt AC 1551 ms 1048 KB