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
2014-06-17 05:46:31+0900
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
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