어흥

문제 링크: https://www.acmicpc.net/problem/1719 1719번: 택배 첫째 줄에 두 수 n과 m이 빈 칸을 사이에 두고 순서대로 주어진다. n은 집하장의 개수로 200이하의 자연수, m은 집하장간 경로의 개수로 10000이하의 자연수이다. 이어서 한 줄에 하나씩 집하장간 경 www.acmicpc.net 1. 주의할 점 - 다익스트라 알고리즘을 이용하면서 어떤 방식으로 경로표를 저장할 것인지 고려한다 2. 구현 - 모든 간선들의 정보를 V[] 벡터에 저장한다 - 1~Node까지 모든 Node를 시작점으로 하여 다익스트라 알고리즘을 수행하면서 경로표를 구할 수 있도록 한다 - 시작점에서 출발하는 겨우 tmp.start를 다음 Node로 설정하고, 이외의 경우에는 tmp.start를..

문제 링크: https://www.acmicpc.net/problem/2211 2211번: 네트워크 복구 첫째 줄에 두 정수 N, M이 주어진다. 다음 M개의 줄에는 회선의 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 컴퓨터와 B번 컴퓨터가 통신 시간이 C (1 ≤ C ≤ 10)인 회선으로 연결되어 있다� www.acmicpc.net 1. 주의할 점 - M의 개수가 주어져 있지 않다 - 정답의 개수는 항상 N-1개다. 즉, Dist[a]+ a->G = Dist[b]+b->G의 값이 같다면, MST를 이루는 간선들로 구하자 2. 구현 - 다익스트라를 통해 Node 1번에서 다른 Node들까지의 최단거리를 구하여 Dist[] 배열에 저장한다 - 최단거리를 이루는 간선을 구할때, 1번 Nod..

문제 링크: https://www.acmicpc.net/problem/10282 10282번: 해킹 문제 최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염�� www.acmicpc.net 1. 주의할 점 - 단방향 그래프다 - 다익스트라 알고리즘을 사용하면 되며, 매 TC마다 V[] 벡터와,Dist[] 배열을 초기화 해줘야 한다 2. 구현 - 입력받는 그래프의 정보를 V[]에 모두 저장한다 - 시작점을 기준으로 우선순위큐를 사용하여 다익스트라 알고리즘을 통해 각 Node까지의 최단거리를 구한다 - 1~Node의 수 만큼 확인하면서 Dist[]값이 Max가 아니면 Cn..

문제 링크: https://www.acmicpc.net/problem/1738 1738번: 골목길 첫째 줄에 골목길들이 교차하는 지점의 개수 n (2 ≤ n ≤ 100)과 골목길의 개수 m (1 ≤ m ≤ 20,000) 이 차례로 주어진다. 이어지는 m개의 행에 각각의 골목길을 나타내는 세 정수 u, v, w가 차례로 �� www.acmicpc.net 1. 주의할 점 - 양의 사이클이 아닌, 가중치를 전부 -1로 곱하여 음의 사이클을 구하도록 한다 - 경로를 어떤 방식으로 저장할 것인가 - 사이클이 있다고 무조건 -1을 출력하는 것이 아니다 -> 도착지점까지 이동중, 음의 사이클이 존재한다면 -1 출력 2. 구현 - 음의 사이클이 존재하므로 벨만포드 알고리즘을 사용한다 - Bellman_ford() 함수..

문제 링크: https://www.acmicpc.net/problem/9370 9370번: 미확인 도착지 문제 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 출발했다는 것, 그리고 목적지 후보들 중 하나가 그들의 목적지라는 것이다. 그들이 급한 상황이기 때문에 목적지까지 우회하지 않고 최단거리로 갈 것이라 확신한다. 이상이다. (취익) 어휴! (요란한 옷차림을 했을지도 모를) 듀오가 어디에도 보이지 않는다. 다 www.acmicpc.net 1. 주의할 점 - 무조건 H-G 도로를 지나가고 후보지까지 최단경로를 갱신했다면 정답에 포함한다 - 매 TC마다 초기..

문제 링크: https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존재하며, 그 거리가 c라는 뜻이다. (1 ≤ c ≤ 1,000) 다음 줄에는 반드시 거쳐야 하는 두 개의 서로 다른 정점 번호 v1과 v2가 주어진다. (v1 ≠ v2, v1 ≠ N, v2 ≠ 1) www.acmicpc.net 1. 주의할 점 - 최소 3번의 다익스트라 알고리즘을 사용해야 한다 - 반드시 지나야 하는점으로 시작점, 도착점 형태로 들어올 수 있다 2. 구현..

문제 링크: https://www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 문제 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주인공, 링크는 지금 도둑루피만 가득한 N x N 크기의 동굴의 제일 왼쪽 위에 있다. [0][0]번 칸이기도 하다. 왜 이런 곳에 들어왔냐고 묻는다면 밖에서 사람들이 자꾸 "젤다의 전설에 나오는 녹색 애가 젤다지?"라고 물어봤기 때문이다. 링크가 녹색 옷을 입 www.acmicpc.net 1. 주의할 점 - 이미 방문했거나, 해당 지점에 도착할때까지 소비한 루피가 많은 경우 방문하지 않는다 ..

문제 링크: https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 그리고 그 다음에는 도착지의 도시 번호가 주어지고 또 그 버스 비용이 주어진다. 버스 비용은 0보다 크거나 같고, 100,000보다 작은 정수이다. 그리고 m+3째 줄에는 우리가 구하고자 하는 구간 출발점의 도시 www.acmicpc.net 1. 주의할 점 - 경로를 출력해야 하므로 역방향의 그래프도 저장해야 한다 - 경로를 찾는 방법은, 특정 조건..