programmer life guidance 101

www.acmicpc.net/problem/1956 1956번: 운동 첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의 www.acmicpc.net 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 2 초 192 MB 6664 3236 2424 46.687% 문제 V개의 마을와 E개의 도로로 구성되어 있는 도시가 있다. 도로는 마을과 마을 사이에 놓여 있으며, 일방 통행 도로이다. 마을에는 편의상 1번부터 V번까지 번호가 매겨져 있다고 하자. 당신은 도로를 따라 운동을 하기 위한 경로를 찾으려고 한다. 운동을 한 후에..

> 플로이드 와샬 알고리즘 Floyd-Warshall algorithm 앞의 두 최단거리 알고리즘과는 다르게 정점 V개가 있고 거리가 다 주어져 있을 때, 단 한번의 시행으로 모든 정점 쌍 사이의 거리를 다 구해낸다. 코드는 굉장히 짧은데, 아주 전형적인 3중 for문의 형태를 하고 있고 O(V^3)입니다. 음의 가중치가 있는 간선 그래프에서도 제대로 동작합니다. -BOJ[11404] : 플로이드 이 문제를 풀 겁니다. 아니 제목부터 대놓고 플로이드입니다. 그러므로 플로이드를 씁시다. 각 정점 u, v 쌍에 대해 u에서 v로 가는 최단 경로를 한 번에 다 구할 것이고, 이를 위해 먼저 2차원 배열 dist를 준비합니다. 초기에는 자기 자신으로 가는 dist[i][i] 꼴은 다 0이고, 나머지는 ∞으로 설..