https://www.acmicpc.net/problem/14284 14284번: 간선 이어가기 2 정점 n개, 0개의 간선으로 이루어진 무방향 그래프가 주어진다. 그리고 m개의 가중치 간선의 정보가 있는 간선리스트가 주어진다. 간선리스트에 있는 간선 하나씩 그래프에 추가해 나갈 것이다. www.acmicpc.net 풀이 1, 양방향이며 최대치는 5억이기에 INF는 10억으로 잡아주었다. 2, 다익스트라 적용 # 14284번 간선 이어가기 2 import heapq import sys input = sys.stdin.readline INF = int(1e9) def dijkstra(start, target): q = [] # heapq.heappush(dist, node) heapq.heappush(q,..

https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 풀이 1, 양방향 문제이다. INF는 10억이기에 int(1e9)로 해주었다. 2, 다익스트라 적용 # 1916번 최소비용 구하기 import heapq import sys input = sys.stdin.readline INF = int(1e9) def dijkstra(start, target): q = [] # heapq.heappush(dist, node) ..

https://www.acmicpc.net/problem/5972 5972번: 택배 배송 농부 현서는 농부 찬홍이에게 택배를 배달해줘야 합니다. 그리고 지금, 갈 준비를 하고 있습니다. 평화롭게 가려면 가는 길에 만나는 모든 소들에게 맛있는 여물을 줘야 합니다. 물론 현서는 www.acmicpc.net 풀이 1, 단방향인것을 주의해서 문제를 풀어주길 바란다. 최대치 또한 고려해서 INF를 sys.maxsize로 고쳐주었다. 2, 다익스트라 적용 # 5972번 택배 배송 import sys import heapq input = sys.stdin.readline INF = sys.maxsize def dijkstra(target): q = [] heapq.heappush(q, (0, 1)) distance[..

https://www.acmicpc.net/problem/17396 17396번: 백도어 첫 번째 줄에 분기점의 수와 분기점들을 잇는 길의 수를 의미하는 두 자연수 N과 M이 공백으로 구분되어 주어진다.(1 ≤ N ≤ 100,000, 1 ≤ M ≤ 300,000) 두 번째 줄에 각 분기점이 적의 시야에 보이는 www.acmicpc.net 풀이 다익스트라 알고리즘 사용해서 풀 수 있는 문제이다. 1 , 이 문제에서 최대는 300억이 나오기에 INF 설정에 주의를 해야한다. 아래 코드에서는 INF를 1000억으로 구성했다. 코드가 더럽지 않게 리스트로 간단히 만들어서 인덱스 비교로 간선 처리를 하려했으나 집합으로 처리해보고 싶어서 처리했다. INF가 무엇인지 모르겠다면 본 블로그 알고리즘을 참고해주세요. 2..