최단 거리 문제이다. 책 풀이는 플로이드-워셜 알고리즘을 활용해서 풀었으나, 나는 다익스트라 알고리즘 같은 느낌의 알고리즘을 사용해서 풀었다. 내 풀이 # 정확한 순위 import sys, heapq input = sys.stdin.readline INF = int(1e9) n, m = map(int, input().split()) # n은 학생 수, m은 두 학생의 성적을 비교한 횟수 graph = [[] for _ in range(n+1)] connected = [[False] * (n+1) for _ in range(n+1)] # connected[i][j] = i->j로 연결되어 있는지 여부를 저장 # 성적 비교 입력 for _ in range(m): a, b = map(int, input().s..
플로이드워셜
37_플로이드 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 happenundo.tistory.com
11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 플로이드-워셜 알고리즘을 알고 있다면 쉽게 풀 수 있는 문제. 플로이드-워셜 알고리즘의 시간복잡도는 O(V^3)인데, 도시 개수가 최대 100개이므로 시간 복잡도도 만족한다. 단, 이 문제에서는 추가된 조건들이 있다. 1. 시작도시와 도착도시가 연결된 노선은 하나가 아닐 수 있다. 2. 마지막에 최단 거리를 출력할 때, 갈 수 없는 경우에는 0을 출력한다. 1번 조건을 만족하기 위해, 이차원 리스트에 거리를 입력할 때, 입력받은 거리가 원래 입력되어 있는 거리보다..
