Submission #1303429
Source Code Expand
using System.Collections; using System.Collections.Generic; using System.IO; using System.Linq; using System.Text; using System; using System.Numerics; using static System.Math; using static System.Console; struct Pair : IComparable<Pair> { public int u, d; public Pair(int u, int d = 0) { this.u = u; this.d = d; } public int CompareTo(Pair x) => d.CompareTo(x.d); } class E { static void Main() => new J(); } class J { int[] G() => ReadLine().Split(new char[] { ' ', '\t' }, StringSplitOptions.RemoveEmptyEntries).Select(int.Parse).ToArray(); public const int INF = 1000000007; int V; List<Pair>[] es; public J() { var I = G(); V = I[0]; int E = I[1], R = I[2], T = I[3]; es = new List<Pair>[V]; for (var i = 0; i < V; i++) es[i] = new List<Pair>(); for (var e = 0; e < E; e++) { I = G(); int a = I[0] - 1, b = I[1] - 1, c = I[2]; es[a].Add(new Pair(b, c)); es[b].Add(new Pair(a, c)); } alld = new int[V, V]; for (var u = 0; u < V; u++) for (var v = 0; v < V; v++) alld[u, v] = INF; for (var u = 0; u < V; u++) alld[u, u] = 0; var s = 0L; for (var u = 0; u < V; u++) { var d = DijkstraFrom(u); Array.Sort(d); var i = 1; for (var x = 1; x < V; x++) { while (i < V && R * d[x] >= T * d[i]) i++; s += V - i; if (i <= x) s--; } } WriteLine(s); } int[] lands; int[,] alld; int[] DijkstraFrom(int u) { var d = new int[V]; for (var i = 0; i < V; i++) d[i] = alld[i, u]; var queue = new PriorityQueue(); queue.Enqueue(new Pair(u)); while (queue.Count > 0) { var p = queue.Dequeue(); var v = p.u; if (d[v] < p.d) continue; foreach (var e in es[v]) { var tmp = d[v] + e.d; if (d[e.u] > tmp) queue.Enqueue(new Pair(e.u, d[e.u] = tmp)); } } //for (var i = 0; i < V; i++) alld[i, u] = alld[u, i] = d[i]; return d; } } class PriorityQueue { List<Pair> list = new List<Pair>(); public int Count; public void Enqueue(Pair x) { var pos = Count++; list.Add(x); while (pos > 0) { var p = (pos - 1) / 2; if (list[p].CompareTo(x) <= 0) break; list[pos] = list[p]; pos = p; } list[pos] = x; } public Pair Dequeue() { var value = list[0]; var x = list[--Count]; list.RemoveAt(Count); if (Count == 0) return value; var pos = 0; while (pos * 2 + 1 < Count) { var a = 2 * pos + 1; var b = 2 * pos + 2; if (b < Count && list[b].CompareTo(list[a]) < 0) a = b; if (list[a].CompareTo(x) >= 0) break; list[pos] = list[a]; pos = a; } list[pos] = x; return value; } }
Submission Info
Submission Time | |
---|---|
Task | C - ウサギとカメ |
User | selpo |
Language | C# (Mono 4.6.2.0) |
Score | 100 |
Code Size | 2662 Byte |
Status | AC |
Exec Time | 3314 ms |
Memory | 64200 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 | 28 ms | 9300 KB |
subtask0_sample-02.txt | AC | 26 ms | 9428 KB |
subtask1_01.txt | AC | 26 ms | 11476 KB |
subtask1_02.txt | AC | 27 ms | 11348 KB |
subtask1_03.txt | AC | 26 ms | 9428 KB |
subtask1_04.txt | AC | 27 ms | 11476 KB |
subtask1_05.txt | AC | 40 ms | 11436 KB |
subtask1_06.txt | AC | 45 ms | 11436 KB |
subtask1_07.txt | AC | 107 ms | 15712 KB |
subtask1_08.txt | AC | 128 ms | 13920 KB |
subtask1_09.txt | AC | 978 ms | 37712 KB |
subtask1_10.txt | AC | 920 ms | 23136 KB |
subtask1_11.txt | AC | 416 ms | 23768 KB |
subtask1_12.txt | AC | 2987 ms | 60108 KB |
subtask1_13.txt | AC | 2960 ms | 58060 KB |
subtask1_14.txt | AC | 3284 ms | 64200 KB |
subtask1_15.txt | AC | 2219 ms | 53840 KB |
subtask1_16.txt | AC | 3314 ms | 62152 KB |