전보 : 최단경로

로직 (플로이드워셜 이용 )

1. n,m,c 입력받기 : 도시개수 , 통로개수 , 도시
2. graph=[]

• 무한으로 초기화
• a,b가 같으면 0으로 초기화
• x,y,z 입력받고 -> garph에 넣어주기

3. 알고리즘 수행

• if graph[c][i] < INF and graph[c][i]!=0 :
  count += 1
• count : 도시 c 와 연결된 도시의 수
• distance : 도시 c 와 연결된 도시 중 가장 긴 거리

4. 결과 출력

코드

# 1
n,m,c = map(int,input().split())

# 2
INF = int(1e9)
graph=[]
graph = [[INF] * (n+1) for _ in range(n+1)]

for a in range(n+1):
  for b in range(n+1):
    if a==b :
      graph[a][b]=0
      graph[b][a]=0

for i in range(m):
  x,y,z= map(int,input().split())
  graph[x][y] = z

# 3
count = 0
distance =0 

for b in range(n+1):
  if graph[c][b] < INF and graph[c][b]!= 0 :
    # count : 연결된 도시의 수 (+1)
    count+=1
    # distance : 가장 먼 거리 출력하기
    distance = max(distance, graph[c][b])

print(count,distance)

주의사항

• 플로이드 워셜 알고리즘을 이용했다
  -> N이 1000을 넘어가기에 시간복잡도에서 걸릴 수도 있다ㅜ
• count , distance 변수의 의미를 잘 보고 로직을 이용한다