[プログラマー]配信(JAVA)

問題の説明

Nの村からなる国があります.この国の村ごとに1からNまで番号が付けられています.それぞれの村は双方向に通行する道を結んでおり、異なる村の間を移動するときはこの道を通らなければならない.道路を通るのにかかる時間は道路によって異なります.今の1番村のレストランから食べ物を各村に送りたいです.各村から注文を受けたいのですが、N村の中でK時間以下に配達できる村でしか注文を受けられないと思います.次に、N=5、K=3の例を示します.
上図1番村のレストランは[1,2,4,5]番村まで3時間以下で配達できます.しかし、3番村までは3時間以内に配送できるルートがないので、3番村は注文を受け付けません.このため、1番村のレストランで出前の注文を受けられる村は4つある.
村落個数N、各村落を結ぶ道路の情報路、配達可能な食べ物の時間Kをパラメータとした場合は、解関数を完了し、食べ物の注文を受けられる村落個数を返してください.

せいげんじょうけん

村の個数Nは1以上50以下の自然数である.
道路の長さ(道路情報の個数)は1または2000以下である.
道路の各要素は、村を結ぶ各道路の情報を表します.
roadは長さ3の配列で,順序(a,b,c)である.
a,b(1≦a,b≦N,a!=b)は道路が接続された2つの村の番号であり、c(1≦c≦10000,cは自然数)は道路を通過するのに要する時間である.
2つの村a,bを結ぶ道は複数ある.
1つの道路の情報は何度も繰り返して、与えることができません.
Kは配送可能な時間を示し、1万または50万以下である.
任意の2つの村の間には常に移動可能な経路がある.
1番村のレストランでK以下の時間内に食事を送れる村の数だけでいいです.

My Code

import java.util.*;
class Solution {
    public int solution(int N, int[][] road, int K) {
        Set<Integer> hs = new HashSet<>();
        hs.add(1);
        int[] visit = new int[N+1];
        Arrays.fill(visit, Integer.MAX_VALUE);
        visit[1] = 0;
        int[][] dists = new int[N+1][N+1];
        for(int i=0 ; i<road.length ; i++) {
            int t1=road[i][0], t2=road[i][1], d=road[i][2];
            dists[t1][t2] = dists[t1][t2]==0?d:Math.min(dists[t1][t2], d);
            dists[t2][t1] = dists[t2][t1]==0?d:Math.min(dists[t2][t1], d);
        }
        Queue<Integer> q = new LinkedList<>();
        q.offer(1);
        while(!q.isEmpty()) {
            int size = q.size();
            for(int i=1 ; i<=size ; i++) {
                int town = q.poll();
                int[] dist = dists[town];
                for(int j=1 ; j<dist.length ; j++) {
                    if(dist[j]==0) continue;
                    if(visit[town]+dist[j]<visit[j] && visit[town]+dist[j]<=K) {
                        q.offer(j);
                        visit[j] = visit[town]+dist[j];
                        hs.add(j);
                    }
                }
            }
        }
        return hs.size();
    }
}

Comment

これは2番です.1 tはDFSで解き,visitを使わずK以下であれば返す.
同様に、5つのテストケースで時間がかかりました.
やはりvisit処理を経て、不要な重複はありません.
考えさせてください.