Submission #1515441
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using weight = double;
constexpr weight INF = 1e9;
struct edge {
int from, to;
weight cost;
bool operator<(edge const& rhs) const {
return cost > rhs.cost;
}
};
using edges = std::vector<edge>;
using graph = std::vector<edges>;
void add_edge(graph& g, int from, int to, weight cost) {
g[from].push_back(edge{from, to, cost});
}
std::vector<weight> dijkstra(graph& g, int s) {
using P = std::pair<weight, int>;
std::vector<weight> d(g.size(), INF);
std::priority_queue<P, std::vector<P>, std::greater<P>> que;
fill(d.begin(), d.end(), INF);
d[s] = 0;
que.push(P{0, s});
while(!que.empty()) {
P p = que.top(); que.pop();
int v = p.second;
if(d[v] < p.first) {
continue;
}
for(int i=0; i<g[v].size(); ++i) {
edge e = g[v][i];
if(d[e.to] > d[v] + e.cost) {
d[e.to] = d[v] + e.cost;
que.push(P{d[e.to], e.to});
}
}
}
return d;
}
int main() {
int N, M;
double R, T;
cin >> N >> M >> R >> T;
graph g(N);
for(int i = 0; i < M; ++i) {
int a, b, c;
cin >> a >> b >> c;
a--; b--;
add_edge(g, a, b, c);
add_edge(g, b, a, c);
}
ll res = 0;
for(int i = 0; i < N; ++i) {
auto d = dijkstra(g, i);
sort(d.begin(), d.end());
for(int j = 1; j < N; ++j) {
auto t = upper_bound(d.begin(), d.end(), d[j] * R / T) - d.begin();
res += N - t - (t <= j);
}
}
cout << res << endl;
}
Submission Info
Submission Time |
|
Task |
C - ウサギとカメ |
User |
Suibaka |
Language |
C++14 (GCC 5.4.1) |
Score |
100 |
Code Size |
1737 Byte |
Status |
AC |
Exec Time |
1171 ms |
Memory |
512 KB |
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 |
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 |
31 ms |
384 KB |
subtask1_08.txt |
AC |
39 ms |
384 KB |
subtask1_09.txt |
AC |
351 ms |
384 KB |
subtask1_10.txt |
AC |
335 ms |
384 KB |
subtask1_11.txt |
AC |
144 ms |
384 KB |
subtask1_12.txt |
AC |
1073 ms |
512 KB |
subtask1_13.txt |
AC |
1070 ms |
512 KB |
subtask1_14.txt |
AC |
1167 ms |
512 KB |
subtask1_15.txt |
AC |
798 ms |
512 KB |
subtask1_16.txt |
AC |
1171 ms |
512 KB |