MuviSsum

www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 문제: 모든 도시에 대해서 도시 A에서 B로 가는데 필요한 비용의 최솟값을 구하라. 문제 이해하기!! 모든 도시로 가는 최소 비용을 구하면 되는 문제입니다. 한 루트의 최소비용을 구할 때는 다익스트라를 쓰지만, 모든 곳의 최소비용을 구할 때는 플로이드 와샬을 쓰면 됩니다. 다만 주의할 점은 정점의 갯수 ** 3 이므로 정점의 갯수가 작을 때 쓸 수 있습니다. 그래서 푼 방법은 1. 처음 받는 루트와 비용을 최소..

www.acmicpc.net/problem/9694 9694번: 무엇을 아느냐가 아니라 누구를 아느냐가 문제다 맨위 첫 번째 줄에 T(1

www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 문제: 파티에 다녀오는 최단 거리(왕복)를 구하라. 문제 이해하기!! 다익스트라 문제였습니다. 하지만 다익스트라를 한 번만에 푸는 것이 아닌 단 방향 길을 양 방향으로 생각해야 되는 문제에요. 시작하는 지점이 여러 개라고 모두 생각하다가는 시간초과가 날 수 있습니다. 제가 푼 방식을 설명하자면, 1. 먼저 도착지점에서 각 마을 파티사람들의 오는 최소거리를 다익스트라로 찾습니다. 2..

www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 문제: 목표 도시로 이동하는 최소비용을 구하여라. 문제 이해하기!! 최소 비용 그래프문제라면 제일 먼저 생각해봐야 할 것! 바로 다익스트라입니다. 이 문제도 다익스트라인데요. 그래프 연결은 상호적 연결이 아니기 때문에 한 쪽만 연결해 줍니다. 그리고 다익스트라로 비용 구하시면 됩니다. 문제 풀어보기!! 일단 문제를 보면 M이 10만까지 가능하기 때문에 input을 stdin.r..