Submission #185571

---

Source Code Expand

using System;
using System.Collections;
using System.Collections.Generic;
 
class Myon
{
    public Myon() { }
    public static int Main()
    {
        new Myon().calc();
        return 0;
    }
 
    List<int>[] l;
    int MAX = 99999999;
 
    void calc()
    {
        string[] st = splitLine(4, 4);
        int N = getInt(st[0], 3, 2500);
        int M = getInt(st[1], 2, 3000);
        int R = getInt(st[2], 1, 200);
        int T = getInt(st[3], 1, 200);
        l = new List<int>[N];
        for (int i = 0; i < N; i++)
        {
            l[i] = new List<int>();
        }
 
        for (int i = 0; i < M; i++)
        {
            st = splitLine(3, 3);
            int a = getInt(st[0], 1, N) - 1;
            int b = getInt(st[1], 1, N) - 1;
            int c = getInt(st[2], 1, 100);
            l[a].Add((b << 8) + c);
            l[b].Add((a << 8) + c);
        }
 
        long ret = 0;
        for (int i = 0; i < N; i++)
        {
            ret += getCount(distset(i), R, T);
        }
        Console.WriteLine(ret);
    }
 
    int[] distset(int start)
    {
        int N =l.Length;
        int[] dist = new int[N];
        for (int i = 0; i < N; i++)
        {
            dist[i] = MAX;
        }
        dist[start] = 0;
        Queue<int> q = new Queue<int>();
        q.Enqueue(start);
        bool[] inqueue = new bool[N];
        while (q.Count != 0)
        {
            int now = q.Dequeue();
            inqueue[now] = false;
            foreach (var item in l[now])
            {
                int to = item >> 8;
                int cost = item & 0xFF;
                if (dist[to] > dist[now] + cost)
                {
                    dist[to] = dist[now] + cost;
                    if (!inqueue[to])
                    {
                        inqueue[to] = true;
                        q.Enqueue(to);
                    }
                }
            }
        }
        Array.Sort(dist);
        return dist;
    }
 
    int getCount(int[] dist, int R, int T)
    {
        int N = dist.Length;
        int ret = 0;
        while (dist[N - 1] == MAX) N--;
        int j = 1;
        for (int i = 1; i < N; i++)
        {
            while (j < N && dist[i] * R >= dist[j] * T) j++;
            if (j >= N) break;
            ret += N - j;
            if (i >= j) ret--;
        }
        return ret;
    }
 
 
    //swap
    void swap<T>(ref T a, ref T b)
    {
        T c = a;
        a = b;
        b = c;
    }
 
    void myon(string s)
    {
        throw new Exception(s);
    }
 
    int getInt(string s, int min, int max)
    {
        int ret = int.Parse(s);
        if (ret < min) throw new Exception("low");
        if (ret > max) throw new Exception("high");
        return ret;
    }
 
    int getIntLine(int min, int max)
    {
        int ret = int.Parse(Console.ReadLine());
        if (ret < min) throw new Exception("low");
        if (ret > max) throw new Exception("high");
        return ret;
    }
 
    double getDouble(string s, double min, double max)
    {
        double ret = double.Parse(s);
        if (ret < min) throw new Exception("low");
        if (ret > max) throw new Exception("high");
        return ret;
    }
 
    double getDoubleLine(double min, double max)
    {
        double ret = double.Parse(Console.ReadLine());
        if (ret < min) throw new Exception("low");
        if (ret > max) throw new Exception("high");
        return ret;
    }
 
    string getString(string s, int min, int max)
    {
        if (s.Length < min) throw new Exception("low");
        if (s.Length > max) throw new Exception("high");
        return s;
    }
 
    string getStringLine(int min, int max)
    {
        string s = Console.ReadLine();
        if (s.Length < min) throw new Exception("low");
        if (s.Length > max) throw new Exception("high");
        return s;
    }
 
    string[] splitLine(int min, int max)
    {
        string[] ret = Console.ReadLine().Split(' ');
        if (ret.Length == 1 && ret[0] == "") ret = new string[0];
        if (ret.Length < min || ret.Length > max) throw new Exception("wrong length");
        return ret;
    }
}

Submission Info

Judge Result