플로이드 워셜 알고리즘

2023. 5. 19. 17:54·Coding Test/Graph
728x90

분석

 

[11403] 경로 찾기 (플로이드-워셜)

11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 분석 최단거리를 구하

karla.tistory.com

 

풀이

"""
N개의 도시가 주어지고, 각 도시들을 연결하는 도로와 해당 도로를 통행하는 비용이 주어질 때
모든 도시에서 모든 도시로 이동하는데 쓰이는 비용의 최소값

첫 번째 줄에는 도시의 수N(N<=100)과 도로수 M(M<=200)가 주어지고,
M줄에 걸쳐 도로정보 와 비용(20 이하의 자연수)이 주어진다. 만약 1번 도시와 2번도시가 연결되고 그 비용이 13이 면 “1 2 13”으로 주어진다.
5 8
1 2 6
1 3 3
3 2 2
2 4 1
2 5 13
3 4 5
4 2 3
4 5 7


모든 도시에서 모든 도시로 이동하는데 드는 최소 비용을 아래와 같이 출력한다.
자기자신으로 가는 비용은 0입니다. i번 정점에서 j번 정점으로 갈 수 없을 때는 비용을 “M"으 로 출력합니다.
0 5 3 6 13
M 2 0 3 10
M 3 M 0 7
M M M M 0
"""
import sys
input=sys.stdin.readline

#도시수, 도로수
n,m = map(int,input().split())

# 인접행렬
d = array = [[sys.maxsize for j in range(n)] for i in range(n)]
for i in range(n):
    d[i][i] = 0

for _ in range(m):
  i,j,w = list(map(int, input().split()))
  d[i-1][j-1]=w

for k in range(n): # 경유지 k
    for s in range(n):
        for e in range(n):
            if d[s][k]!= sys.maxsize and d[k][e]!= sys.maxsize :
                d[s][e]=min(d[s][e], d[s][k]+d[k][e])
# print(d)

for i in range(n):
    for j in range(n):
        print(d[i][j] if d[i][j]!=sys.maxsize else "M", end=" ")
    print()

 

 

 

728x90
저작자표시 비영리 변경금지 (새창열림)
'Coding Test/Graph' 카테고리의 다른 글
  • 위상정렬(그래프 정렬)
  • 회장뽑기 (플로이드 워셜)
  • 사다리 타기 (DFS)
  • [7576] 토마토 (BFS)
Karla Ko
Karla Ko
𝘾𝙤𝙣𝙩𝙞𝙣𝙪𝙤𝙪𝙨𝙡𝙮 𝙄𝙢𝙥𝙧𝙤𝙫𝙞𝙣𝙜, 𝘾𝙤𝙣𝙨𝙩𝙖𝙣𝙩𝙡𝙮 𝘿𝙚𝙫𝙚𝙡𝙤𝙥𝙞𝙣𝙜 𝙔𝙚𝙨!
    250x250
  • Karla Ko
    karlaLog
    Karla Ko
  • 전체
    오늘
    어제
    • Total (467)
      • Spring (19)
      • JPA (4)
      • Cloud & Architecture (15)
        • Kubernetes (5)
        • Docker (3)
        • MSA (2)
        • GCP (1)
        • AWS (4)
      • Devops (1)
      • Message Queue (4)
        • Kafka (2)
        • RabbitMQ (2)
      • Git (4)
      • DB (4)
      • Java (9)
      • Python (4)
      • CS (11)
        • OS (8)
        • Network (2)
        • Algorithm (1)
      • Coding Test (392)
        • programmers (156)
        • Graph (43)
        • DP (37)
        • Search (31)
        • Tree (13)
        • Data Structure (26)
        • Combination (12)
        • Implement (18)
        • Geedy (23)
        • Sort (7)
        • Math (21)
        • geometry (2)
  • 블로그 메뉴

    • 홈
  • 링크

  • 공지사항

  • 인기 글

  • 태그

    프로그래머스
    큐
    최대공약수
    알고리즘
    트리
    구현
    다익스트라
    그리디
    DP
    덱
    재귀
    힙
    월간코드챌린지
    백준
    이분탐색
    스택
    플로이드워셜
    정렬
    조합
    DFS
    Algorithm
    BFS
    그래프
    최단거리
    동적계획법
    파이썬
    자료구조
    최소신장트리
    구간합
    LIS
  • hELLO· Designed By정상우.v4.10.3
Karla Ko
플로이드 워셜 알고리즘
상단으로

티스토리툴바