Submission #1609615
Source Code Expand
import std.algorithm, std.conv, std.range, std.stdio, std.string; import std.bitmanip; // BitArray alias graph = Graph!(int, size_t); void main() { auto rd1 = readln.split.to!(size_t[]), n = rd1[0], m = rd1[1]; struct Edge { size_t a, b; int c; } auto e = new Edge[](m); auto g = new int[][](n, n); foreach (i; 0..n) { g[i][] = graph.inf; g[i][i] = 0; } foreach (i; 0..m) { auto rd2 = readln.splitter; auto a = rd2.front.to!size_t-1; rd2.popFront(); auto b = rd2.front.to!size_t-1; rd2.popFront(); auto c = rd2.front.to!int; e[i] = Edge(a, b, c); g[a][b] = g[b][a] = c; } auto d = graph.floydWarshal(g); auto ans = BitArray(); ans.length = m; foreach (i; 0..n) foreach (j; 0..m) { auto a = e[j].a, b = e[j].b, c = e[j].c; if (d[i][a] + c == d[i][b] || d[i][b] + c == d[i][a]) ans[j] = true; } writeln(m - ans.bitsSet.walkLength); } template Graph(Wt, Node, Wt _inf = 10 ^^ 9, Node _sent = Node.max) { import std.algorithm, std.array, std.conv; const inf = _inf, sent = _sent; Wt[][] floydWarshal(Wt[][] g) { Wt[][] dist; Node[][] inter; floydWarshal(g, dist, inter); return dist; } void floydWarshal(Wt[][] g, out Wt[][] dist, out Node[][] inter) { auto n = g.length; dist = g.map!(i => i.dup).array; inter = new Node[][](n, n); foreach (i; 0..n) inter[i][] = sent; foreach (k; 0..n) foreach (i; 0..n) foreach (j; 0..n) if (dist[i][j] > dist[i][k] + dist[k][j]) { dist[i][j] = dist[i][k] + dist[k][j]; inter[i][j] = k.to!Node; } } }
Submission Info
Submission Time | |
---|---|
Task | D - Candidates of No Shortest Paths |
User | tesh |
Language | D (DMD64 v2.070.1) |
Score | 400 |
Code Size | 1718 Byte |
Status | AC |
Exec Time | 5 ms |
Memory | 508 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 400 / 400 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | sample_01.txt, sample_02.txt |
All | sample_01.txt, sample_02.txt, subtask_1_01.txt, subtask_1_02.txt, subtask_1_03.txt, subtask_1_04.txt, subtask_1_05.txt, subtask_1_06.txt, subtask_1_07.txt, subtask_1_08.txt, subtask_1_09.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_20.txt, subtask_1_21.txt, subtask_1_22.txt, subtask_1_23.txt, subtask_1_24.txt, subtask_1_25.txt, subtask_1_26.txt, subtask_1_27.txt, subtask_1_28.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
sample_01.txt | AC | 1 ms | 256 KB |
sample_02.txt | AC | 1 ms | 256 KB |
subtask_1_01.txt | AC | 1 ms | 256 KB |
subtask_1_02.txt | AC | 1 ms | 380 KB |
subtask_1_03.txt | AC | 3 ms | 508 KB |
subtask_1_04.txt | AC | 3 ms | 508 KB |
subtask_1_05.txt | AC | 4 ms | 508 KB |
subtask_1_06.txt | AC | 1 ms | 256 KB |
subtask_1_07.txt | AC | 2 ms | 380 KB |
subtask_1_08.txt | AC | 3 ms | 508 KB |
subtask_1_09.txt | AC | 3 ms | 508 KB |
subtask_1_10.txt | AC | 3 ms | 508 KB |
subtask_1_11.txt | AC | 1 ms | 256 KB |
subtask_1_12.txt | AC | 2 ms | 380 KB |
subtask_1_13.txt | AC | 3 ms | 508 KB |
subtask_1_14.txt | AC | 3 ms | 508 KB |
subtask_1_15.txt | AC | 3 ms | 508 KB |
subtask_1_16.txt | AC | 1 ms | 256 KB |
subtask_1_17.txt | AC | 1 ms | 256 KB |
subtask_1_18.txt | AC | 1 ms | 380 KB |
subtask_1_19.txt | AC | 2 ms | 380 KB |
subtask_1_20.txt | AC | 1 ms | 256 KB |
subtask_1_21.txt | AC | 1 ms | 256 KB |
subtask_1_22.txt | AC | 2 ms | 380 KB |
subtask_1_23.txt | AC | 2 ms | 380 KB |
subtask_1_24.txt | AC | 4 ms | 508 KB |
subtask_1_25.txt | AC | 2 ms | 380 KB |
subtask_1_26.txt | AC | 3 ms | 508 KB |
subtask_1_27.txt | AC | 5 ms | 508 KB |
subtask_1_28.txt | AC | 4 ms | 508 KB |