1759 암호만들기, 5719 거의 최단 경로, 1774 우주신과의 교감

 

1759 암호만들기, 5719 거의 최단 경로, 1774 우주신과의 교감

 

1759 암호만들기

# 첫번째 풀이
import copy

result = []
string = []
visited = []

def combination(array, length, index):
	if len(string) == length:
		result.append(copy.deepcopy(string))
		return
	for i in range(index, len(array)):
		if i in visited:
			continue
		string.append(array[i])
		visited.append(i)
		combination(array, length, i+1)
		string.pop()
		visited.pop()
		
vowels = ('a', 'e', 'i', 'o', 'u')
l, c = map(int, input().split())

array = input().split()
array.sort()

combination(array, l, 0)

for password in result:
	count = 0
	for i in password:
		if i in vowels:
			count += 1
			
	if count >= 1 and count <= l - 2:
		print(''.join(password))
        
# 두번째 풀이(파이썬 라이브러리 활용)
from itertools import combinations

vowels = ('a', 'e', 'i', 'o', 'u')
l, c = map(int, input().split())

array = input().split()
array.sort()

for password in combinations(array, l):
	count = 0
	for i in password:
		if i in vowels:
			count += 1
			
	if count >= 1 and count <= l - 2:
		print(''.join(password))

 

 

5719 거의 최단 경로

# 답은 나오나 메모리 초과, 시간 초과
from collections import deque
import heapq
import sys
input = sys.stdin.readline
def dijkstra():
	heap_data = []
	heapq.heappush(heap_data, (0, start))
	distance[start] = 0
	while heap_data:
		dist, now = heapq.heappop(heap_data)
		if distance[now] < dist:
			continue
		for i in adj[now]:
			cost = dist + i[1]
			if distance[i[0]] > cost and not dropped[now][i[0]]:
				distance[i[0]] = cost
				heapq.heappush(heap_data, (cost, i[0]))
				
def bfs():
	q = deque()
	q.append(end)
	while q:
		now = q.popleft()
		if now == start:
			continue
		for prev, cost in reverse_adj[now]:
			if distance[now] == distance[prev] + cost:
				dropped[prev][now] = True
				q.append(prev)
				
while True:
	n, m = map(int, input().split())
	if n == 0:
		break
	start, end = map(int, input().split())
	adj = [[] for _ in range(n+1)]
	reverse_adj = [[] for _ in range(n+1)]
	for _ in range(m):
		x, y, cost = map(int, input().split())
		adj[x].append((y, cost))
		reverse_adj[y].append((x, cost))
	dropped = [[False] * (n+1) for _ in range(n+1)]
	distance = [1e9] * (n+1)
	dijkstra()
	bfs()
	distance = [1e9] * (n+1)
	dijkstra()
	if distance[end] != 1e9:
		print(distance[end])
	else:
		print(-1)

 

1774 우주신과의 교감

 

import math
import sys
input = sys.stdin.readline

def get_distance(p1, p2):
	a = p1[0] - p2[0]
	b = p1[1] - p2[1]
	return math.sqrt((a * a) + (b * b))
	
def get_parent(parent, n):
	if parent[n] == n:
		return n
	return get_parent(parent, parent[n])
	
def union_parent(parent, a, b):
	a = get_parent(parent, a)
	b = get_parent(parent, b)
	if a < b:
		parent[b] = a
	else:
		parent[a] = b
		
def find_parent(parent, a, b):
	a = get_parent(parent, a)
	b = get_parent(parent, b)
	if a == b:
		return True
	else:
		return False
		
edges = []
parent = {}
locations = []
n, m = map(int, input().split())

for _ in range(n):
	x, y = map(int, input().split())
	locations.append((x, y))
	
length = len(locations)

for i in range(length - 1):
	for j in range(i+1, length):
		edges.append((i+1, j+1, get_distance(locations[i], locations[j])))

for i in range(1, n+1):
	parent[i] = i
	
for i in range(m):
	a, b = map(int, input().split())
	union_parent(parent, a, b)
	
edges.sort(key=lambda data: data[2])

result = 0
for a, b, cost in edges:
	if not find_parent(parent, a, b):
		union_parent(parent, a, b)
		result += cost
		
print('%0.2f' % result)