최단경로

https://www.acmicpc.net/problem/9370 9370번: 미확인 도착지 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 www.acmicpc.net 풀이 다익스트라 알고리즘을 사용했으며 문제에서 목적지까지 최단경로로 이동하는데 주어진 교차로를 무조건 지나야한다. 출발지 - g - h - 목적지 혹은 출발지 - h - g - 목적지가 출발지 - 목적지까지의 최단경로와 동일하다면 교차로를 지나가는것이다. 다만 교차로를 지나가지않는데도 최단경로 값이 같을 수 있지않나 싶다.(입력값이 그렇게 주어진다면..) 다른분들의 풀이를 보니 지나가야하는 ..

https://www.acmicpc.net/problem/1865 1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net 풀이 음수간선이 포함되었기에 벨만 포드 알고리즘을 사용한다. 만일 n번의 시도에서도 최단경로간 갱신된다면 음수간선이 존재한다. # 1865번 웜홀 import sys input = sys.stdin.readline INF = int(1e9) def bf(): distance = [INF] * (n+1) # 시작 노드에 대해서 초기화 distance[1] = 0 # 전체 n번의 라운드(..

https://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, 단방향문제 최대값이 문제없어서 INF는 10억을 잡아주었다. 2, 각 경우의 수의 distance를 받아서 마을 ->파티 경로랑 파티 -> 마을 경로를 더해서 비교해준다. 마무리만 잘해주면 된다. # 1238번 파티 import sys import heapq input = sys.stdin.readline INF = int(1e9) def dijkstra(..

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..