Submission #1381337
Source Code Expand
using System.Collections.Generic; using System.Linq; using System; class Z { static void Main() { new K(); } } class K { public const int INF = 1000000007; int V, R, T, C; readonly List<E>[] es; long s; public K() { var I = G(); V = I[0]; int E = I[1]; R = I[2]; T = I[3]; es = new List<E>[V]; var deg = new int[V]; for (var i = 0; i < V; i++) es[i] = new List<E>(); for (var e = 0; e < E; e++) { I = G(); AddEdge(I[0] - 1, I[1] - 1, I[2]); } for (var u = 0; u < V; u++) Calc(DijkstraFrom(u)); Console.WriteLine(s); } void Calc(List<int> d) { var i = 1; for (var x = 1; x < V; x++) { var t = R * d[x] / T; while (i < V && t >= d[i]) i++; if (i == V) return; s += V - i; if (i <= x) s--; } } void AddEdge(int f, int t, int c) { es[f].Add(new E(t, c)); es[t].Add(new E(f, c)); C = Math.Max(C, c); } List<int> DijkstraFrom(int from) { var d = new int[V]; for (var i = 0; i < V; i++) d[i] = INF; var queue = new DialQueue(C); d[from] = 0; queue.Add(from, 0); var ret = new List<int>(); while (queue.Any) { var p = queue.Pop(); var v = p.To; if (d[v] < p.Cost) continue; ret.Add(d[v]); foreach (var e in es[v]) { var tmp = d[v] + e.Cost; if (d[e.To] > tmp) { if (d[e.To] != INF) queue.Move(e.To, d[e.To], tmp); else queue.Add(e.To, tmp); d[e.To] = tmp; } } } return ret; } static List<int> G() { var line = Console.ReadLine(); var ans = new List<int>(); var n = 0; foreach (var c in line) { if (c == ' ') { ans.Add(n); n = 0; } else n = 10 * n + (c - '0'); } ans.Add(n); return ans; } } struct E { public readonly int To, Cost; public E(int t, int c) { To = t; Cost = c; } } class DialQueue { public int Count { get; private set; } readonly int C; int offset; readonly HashSet<int>[] buckets; HashSet<int> this[int n] { get { return buckets[(n - offset + offset % C) % C]; } } public DialQueue(int c) { C = c + 1; buckets = new HashSet<int>[C]; for (var i = 0; i < C; i++) buckets[i] = new HashSet<int>(); } public void Add(int v, int d) { Count++; this[d].Add(v); } public void Move(int v, int prev, int now) { this[prev].Remove(v); this[now].Add(v); } public bool Any { get { return Count > 0; } } public E Pop() { Count--; var t = offset; while (true) { var s = this[t]; if (s.Count > 0) { var v = s.First(); s.Remove(v); return new E(v, offset = t); } t++; } } }
Submission Info
Submission Time | |
---|---|
Task | C - ウサギとカメ |
User | selpo |
Language | C# (Mono 4.6.2.0) |
Score | 100 |
Code Size | 2668 Byte |
Status | AC |
Exec Time | 2443 ms |
Memory | 39344 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 | 11476 KB |
subtask0_sample-02.txt | AC | 28 ms | 11476 KB |
subtask1_01.txt | AC | 28 ms | 11476 KB |
subtask1_02.txt | AC | 28 ms | 9312 KB |
subtask1_03.txt | AC | 29 ms | 11476 KB |
subtask1_04.txt | AC | 28 ms | 9312 KB |
subtask1_05.txt | AC | 39 ms | 13408 KB |
subtask1_06.txt | AC | 43 ms | 15576 KB |
subtask1_07.txt | AC | 84 ms | 15820 KB |
subtask1_08.txt | AC | 98 ms | 13764 KB |
subtask1_09.txt | AC | 692 ms | 30420 KB |
subtask1_10.txt | AC | 610 ms | 33244 KB |
subtask1_11.txt | AC | 284 ms | 13980 KB |
subtask1_12.txt | AC | 2004 ms | 35248 KB |
subtask1_13.txt | AC | 1978 ms | 39344 KB |
subtask1_14.txt | AC | 2379 ms | 35088 KB |
subtask1_15.txt | AC | 1594 ms | 36176 KB |
subtask1_16.txt | AC | 2443 ms | 39268 KB |