728x90
https://school.programmers.co.kr/learn/courses/30/lessons/12978
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
분석
[11404번] 가장 빠른 버스 노선 구하기(그래프, 최단거리 , 플로이드)
11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발
karla.tistory.com
풀이
import sys
def solution(N, road, K):
answer = 0
d = [[sys.maxsize for j in range(N+1)] for i in range(N+1)]
for i in range(1, N+1):
d[i][i] = 0
g=[[]*(N+1) for _ in range(N+1)]
for s,e,w in road:
if d[s][e]>w:
d[s][e]=w
if d[e][s]>w:
d[e][s]=w
for k in range(1,N+1):
for i in range(1,N+1):
for j in range(1,N+1):
d[i][j]=min(d[i][k]+d[k][j], d[i][j])
for i in range(N+1):
if d[1][i]<=K:
answer+=1
return answer
728x90