Submission #1441133
Source Code Expand
#include <bits/stdc++.h>
#define repeat(i, n) for( int i = 0; (i) < (n); ++(i) )
#define repeat_to(i, n) for( int i = 0; (i) <= (n); ++(i) )
#define repeat_from(i, m, n) for( int i = (m); (i) < (n); ++(i) )
#define repeat_from_to(i, m, n) for( int i = (m); (i) <= (n); ++(i) )
#define repeat_from_reverse(i, m, n) for( int i = (n) - 1; (i) >= (m); --(i) )
#define dump(x) cout << " " << #x << "=" << x
#define vdump(v) for(size_t t=0; t<v.size(); ++t){cout << " " << #v << "[" << t << "]=" << v[t];} cout << endl
using namespace std;
using lint = long long;
/****************** グラフ ******************/
// 諸宣言
using Weight = int;
using Flow = int;
struct Edge {
int src, dst;
Weight weight;
Flow cap;
Edge() : src(0), dst(0), weight(0) {}
Edge(int s, int d, Weight w) : src(s), dst(d), weight(w) {}
};
using Edges = std::vector<Edge>;
using Graph = std::vector<Edges>;
using Array = std::vector<Weight>;
using Matrix = std::vector<Array>;
void add_edge(Graph &g, int a, int b, Weight w = 1) {
g[a].emplace_back(a, b, w);
g[b].emplace_back(b, a, w);
}
void add_arc(Graph &g, int a, int b, Weight w = 1) { g[a].emplace_back(a, b, w); }
// ダイクストラ法(プライオリティーキュー)O((E+V)logV)
std::vector<Weight> dijkstra(const Graph &g, int s) {
const Weight INF = std::numeric_limits<Weight>::max() / 8;
using state = std::tuple<Weight, int>;
std::priority_queue<state> q;
std::vector<Weight> dist(g.size(), INF);
dist[s] = 0;
q.emplace(0, s);
while (q.size()) {
Weight d;
int v;
std::tie(d, v) = q.top();
q.pop();
d *= -1;
/* if(v == t) return d; */
if (dist[v] < d) continue;
for (auto &e : g[v]) {
if (dist[e.dst] > dist[v] + e.weight) {
dist[e.dst] = dist[v] + e.weight;
q.emplace(-dist[e.dst], e.dst);
}
}
}
return dist;
}
int main(void) {
int n, m;
double r, t;
cin >> n >> m >> r >> t;
Graph g(n);
repeat(i, m) {
int a, b, c;
cin >> a >> b >> c;
--a; --b;
add_edge(g, a, b, c);
}
int ans = 0;
repeat(i, n) {
vector<Weight> res = dijkstra(g, i);
vector<double> rab(n), tur(n);
repeat(j, n) {
rab[j] = res[j] / r;
tur[j] = res[j] / t;
}
sort(rab.begin(), rab.end());
//dump(r); dump(t); cout << endl; vdump(res); vdump(rab); vdump(tur);
repeat(j, n) {
if(i == j) continue;
auto ub = upper_bound(rab.begin(), rab.end(), tur[j]);
auto d = distance(ub, rab.end());
ans += d;
if(r < t && d > 0) --ans;
//dump(i); dump(j); cout << " " << distance(ub, rab.end()) << endl;
}
}
cout << ans << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
C - ウサギとカメ |
User |
maphylageo |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
2966 Byte |
Status |
WA |
Exec Time |
1370 ms |
Memory |
512 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
0 / 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 |
30 ms |
384 KB |
subtask1_08.txt |
AC |
39 ms |
384 KB |
subtask1_09.txt |
AC |
336 ms |
384 KB |
subtask1_10.txt |
AC |
334 ms |
384 KB |
subtask1_11.txt |
AC |
137 ms |
384 KB |
subtask1_12.txt |
WA |
1312 ms |
512 KB |
subtask1_13.txt |
WA |
1317 ms |
512 KB |
subtask1_14.txt |
WA |
1326 ms |
512 KB |
subtask1_15.txt |
AC |
778 ms |
512 KB |
subtask1_16.txt |
WA |
1370 ms |
512 KB |