레이팅 미적용설명
정점 \(N\)개와 간선 \(M\)개로 이루어진 무방향 가중치 그래프(모든 가중치는 양수)와 정수 \(D\)가 주어진다. 정점 \(1\)로부터 최단 거리가 \(D\) 이하인 정점(정점 \(1\) 자신 포함)의 개수를 세시오.
제약
입력 형식
첫째 줄에 \(N\)과 \(M\)이 주어진다 (\(1 \le N \le 200\), \(0 \le M \le 800\)). 다음 \(M\)개의 줄에는 무방향 간선 \(u\ v\ w\)가 주어진다 (\(1 \le w \le 100\)). 마지막 줄에는 \(D\)가 주어진다 (\(0 \le D \le 300\)).
출력 형식
정점 \(1\)로부터 거리가 \(D\) 이하인 정점의 개수를 출력한다.
예제 1
입력
4 3
1 2 2
2 3 2
3 4 2
3
출력
2
예제 2
입력
4 2
1 2 5
3 4 1
5
출력
2
예제 3
입력
3 2
1 2 10
2 3 10
0
출력
1
문제 정보
riseoj 작성
출처 RiseOJ Basics
태그