Submission #1754562
Source Code Expand
import std.algorithm, std.conv, std.range, std.stdio, std.string;
alias graph = Graph!(int, int);
alias edge = graph.Edge;
void main()
{
auto rd = readln.split.to!(int[]), n = rd[0], m = rd[1], r = rd[2], t = rd[3];
auto g = new edge[][](n);
foreach (i; 0..m) {
auto rd2 = readln.splitter;
auto a = rd2.front.to!int-1; rd2.popFront();
auto b = rd2.front.to!int-1; rd2.popFront();
auto c = rd2.front.to!int;
g[a] ~= edge(a, b, c);
g[b] ~= edge(b, a, c);
}
auto ans = 0L;
foreach (a; 0..n) {
auto d = graph.dijkstra(g, a);
auto dr = d.dup;
dr[] *= t;
auto drs = dr.sort();
foreach (b; 0..n) {
if (a == b) continue;
auto c = drs.upperBound(d[b] * r).length;
if (r < t)
ans += max(c-1, 0);
else
ans += c;
}
}
writeln(ans);
}
template Graph(Wt, Node, Wt _inf = 10 ^^ 9, Node _sent = Node.max)
{
import std.container;
const inf = _inf, sent = _sent;
struct Edge
{
Node src, dst;
Wt wt;
}
Wt[] dijkstra(Edge[][] g, Node s)
{
Wt[] dist;
Node[] prev;
dijkstra(g, s, dist, prev);
return dist;
}
void dijkstra(Edge[][] g, Node s, out Wt[] dist, out Node[] prev)
{
auto n = g.length;
dist = new Wt[](n);
dist[] = inf;
dist[s] = 0;
prev = new Node[](n);
prev[] = sent;
auto q = heapify!("a.wt > b.wt")(Array!Edge(Edge(sent, s, 0)));
while (!q.empty) {
auto e = q.front; q.removeFront();
if (prev[e.dst] != sent) continue;
prev[e.dst] = e.src;
foreach (f; g[e.dst]) {
auto w = e.wt + f.wt;
if (dist[f.dst] > w) {
dist[f.dst] = w;
q.insert(Edge(f.src, f.dst, w));
}
}
}
}
}
Submission Info
Submission Time |
|
Task |
C - ウサギとカメ |
User |
tesh |
Language |
D (DMD64 v2.070.1) |
Score |
100 |
Code Size |
1818 Byte |
Status |
AC |
Exec Time |
5634 ms |
Memory |
4604 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 |
27 ms |
892 KB |
subtask1_06.txt |
AC |
37 ms |
892 KB |
subtask1_07.txt |
AC |
155 ms |
1276 KB |
subtask1_08.txt |
AC |
193 ms |
1276 KB |
subtask1_09.txt |
AC |
1637 ms |
4604 KB |
subtask1_10.txt |
AC |
1497 ms |
4476 KB |
subtask1_11.txt |
AC |
691 ms |
4476 KB |
subtask1_12.txt |
AC |
5094 ms |
4476 KB |
subtask1_13.txt |
AC |
5049 ms |
4476 KB |
subtask1_14.txt |
AC |
5508 ms |
4604 KB |
subtask1_15.txt |
AC |
3697 ms |
4604 KB |
subtask1_16.txt |
AC |
5634 ms |
4604 KB |