Submission #1303409


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)
	{
		this.u = u;
		this.d = d;
	}
	public int CompareTo(Pair x)
	{
		return d.CompareTo(x.d);
	}
}
class E { static void Main() => new J(); }
class J
{
	int F() => int.Parse(ReadLine());
	int[] G() => ReadLine().Split(new char[] { ' ', '\t' }, StringSplitOptions.RemoveEmptyEntries).Select(int.Parse).ToArray();
	public const int INF = 1000000007;
	public J()
	{
		SetOut(new StreamWriter(OpenStandardOutput()) { AutoFlush = false });
		Solve();
		Out.Flush();
	}
	int V;
	List<Pair>[] es;
	void Solve()
	{
		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));
		}
		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 && (long)R * d[x] >= (long)T * d[i]) i++;
				s += V - i;
				if (i <= x) s--;
			}
		}
		Console.WriteLine(s);
	}
	int[] DijkstraFrom(int u)
	{
		var d = Enumerable.Repeat(INF, V).ToArray();
		var queue = new PriorityQueue();
		d[u] = 0;
		queue.Enqueue(new Pair(u, 0));
		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));
			}
		}
		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;
	}
	public bool IsEmpty => Count == 0;
}

Submission Info

Submission Time
Task C - ウサギとカメ
User selpo
Language C# (Mono 4.6.2.0)
Score 100
Code Size 2637 Byte
Status AC
Exec Time 3384 ms
Memory 41760 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 100 / 100
Status
AC × 2
AC × 18
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 27 ms 13524 KB
subtask0_sample-02.txt AC 27 ms 11476 KB
subtask1_01.txt AC 27 ms 11476 KB
subtask1_02.txt AC 27 ms 9300 KB
subtask1_03.txt AC 27 ms 9300 KB
subtask1_04.txt AC 27 ms 11348 KB
subtask1_05.txt AC 41 ms 11348 KB
subtask1_06.txt AC 47 ms 11476 KB
subtask1_07.txt AC 108 ms 15568 KB
subtask1_08.txt AC 132 ms 17616 KB
subtask1_09.txt AC 997 ms 38988 KB
subtask1_10.txt AC 936 ms 32324 KB
subtask1_11.txt AC 421 ms 23376 KB
subtask1_12.txt AC 3050 ms 37088 KB
subtask1_13.txt AC 3019 ms 39136 KB
subtask1_14.txt AC 3332 ms 39712 KB
subtask1_15.txt AC 2257 ms 37572 KB
subtask1_16.txt AC 3384 ms 41760 KB