개발하는 사막여우

https://www.acmicpc.net/problem/14618 14618번: 총깡 총깡 입력의 첫 번째 줄에 전체 집의 수 N과 집과 집사이를 연결하는 도로 M이 공백으로 주어진다. (3 ≤ N ≤ 5,000, 3 ≤ M ≤ 20,000) 입력의 둘째 줄에 진서의 집 J가 주어진다 (1 ≤ J ≤ N) 입력의 셋째 줄 www.acmicpc.net 소스코드 import sys import heapq as hq input = sys.stdin.readline def dijkstra1(): q = [] min_dis = [float('inf') for _ in range(n+1)] for x in A: # A형 집들 중에서 진서집까지의 최단거리 구하기 min_dis[x] = 0 hq.heappush(q,..

https://www.acmicpc.net/problem/23801 23801번: 두 단계 최단 경로 2 첫째 줄에 정점의 수 N (10 ≤ N ≤ 100,000), 간선의 수 M (10 ≤ M ≤ 300,000)이 주어진다. 다음 M개 줄에 간선 정보 u v w가 주어지며 도시 u와 도시 v 사이의 가중치가 정수 w인 양방향 도로를 나타 www.acmicpc.net 소스코드 import sys import heapq as hq input = sys.stdin.readline def dijkstra(start): q = [] min_dis = [float('inf') for _ in range(n+1)] min_dis[start] = 0 hq.heappush(q,[0,start]) while q: cur..

https://www.acmicpc.net/problem/16167 16167번: A Great Way 첫 번째 줄에 거점의 수 N과 경로의 개수 R이 주어진다. (2 ≤ N ≤ 100, 1 ≤ R ≤ 200) 모든 거점에는 1부터 N까지 번호가 매겨져 있으며 중앙대학교는 1번, 숭실대학교는 N번이다. 두 번째 줄부터는 R www.acmicpc.net 소스코드 import sys import heapq as hq input = sys.stdin.readline def dijkstra(start): q = [] min_dis = [float('inf') for _ in range(n+1)] min_dis[start] = 0 hq.heappush(q,[0,start]) while q: cost,node = ..

https://www.acmicpc.net/problem/17835 17835번: 면접보는 승범이네 첫째 줄에 도시의 수 N(2 ≤ N ≤ 100,000), 도로의 수 M(1 ≤ M ≤ 500,000), 면접장의 수 K(1 ≤ K ≤ N)가 공백을 두고 주어진다. 도시는 1번부터 N번까지의 고유한 번호가 매겨진다. 다음 M개의 줄에 걸쳐 www.acmicpc.net 소스코드 import sys import heapq as hq input = sys.stdin.readline def dijkstra(): q = [] min_dis = [float('inf') for _ in range(n+1)] for i in test: # 우선순위 큐에 한번에 다 넣고 실행 min_dis[i] = 1 hq.heappus..

https://www.acmicpc.net/problem/14221 14221번: 편의점 처음 줄에는 정점의 개수 n, 간선의 개수 m이 주어진다.(2 ≤ n ≤ 5,000, 1 ≤ m ≤ 100,000) 다음 m줄에는 a,b,c가 주어지는데 이는 a, b를 잇는 간선의 거리가 c라는 것이다.(1 ≤ a, b ≤ n, 1 ≤ c ≤ 10,000) www.acmicpc.net 소스코드 import sys import heapq as hq input = sys.stdin.readline def dijkstra(): q = [] min_dis = [float('inf') for _ in range(n+1)] for store in stores: # 편의점의 위치를 한번에 우선순위 큐에 넣어줌 hq.heappu..

https://www.acmicpc.net/problem/5944 5944번: Apple Delivery Bessie has two crisp red apples to deliver to two of her friends in the herd. Of course, she travels the C (1 pa2 -> pa1으로 가는 경로 result = min(ans1,ans2) print(result) 풀이 ★ pb라는 출발점에서 시작하여 pa1, pa2를 거치는 최단 경로를 찾아주면 됩니다. 이 때 목적지가 따로 없어서 헷갈릴 수도 있는데, pa2 or pa1에 도달하면 끝나기 때문에 이 둘을 각각의 케이스의 목적지로 생각해주면 됩니다. ★ 두 정점을 거치는 방법은 2가지가 있습니다. 1. pb -> p..

https://www.acmicpc.net/problem/6248 6248번: Bronze Cow Party One cow from each of N farms (1

https://www.acmicpc.net/problem/9694 9694번: 무엇을 아느냐가 아니라 누구를 아느냐가 문제다 맨위 첫 번째 줄에 T(1 cur_dis + next_dis: min_dis[next_node] = cur_dis + next_dis pre_node[next_node] = cur_node # 역추적을 위해 이전경로 저장 hq.heappush(q,[cur_dis + next_dis, next_node]) return min_dis t = int(input()) for tc in range(1,t+1): n,m = map(int,input().split()) graph = [[] for _ in range(m)] pre_node = [0] * m for _ in range(n): x..

https://www.acmicpc.net/problem/9370 9370번: 미확인 도착지 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 www.acmicpc.net 소스코드 import sys import heapq as hq input = sys.stdin.readline def dijkstra(start): q = [] min_dis = [int(1e9) for _ in range(n+1)] hq.heappush(q,[0,start]) min_dis[start] = 0 while q: cur_dis,cur_node = hq.heappop(q) if ..

https://www.acmicpc.net/problem/27008 27008번: Checking an Alibi A crime has been comitted: a load of grain has been taken from the barn by one of FJ's cows. FJ is trying to determine which of his C (1 ≤ C ≤ 100) cows is the culprit. Fortunately, a passing satellite took an image of his farm M (1 ≤ M ≤ 70000) se www.acmicpc.net 소스코드 import sys import heapq as hq input = sys.stdin.readline def dij..