[백준 1162] python 도로포장

https://www.acmicpc.net/problem/1162 1162번: 도로포장 첫 줄에는 도시의 수 N(1 ≤ N ≤ 10,000)과 도로의 수 M(1 ≤ M ≤ 50,000)과 포장할 도로의 수 K(1 ≤ K ≤ 20)가 공백으로 구분되어 주어진다. M개의 줄에 대해 도로가 연결하는 두 도시와 도로를 통과하 www.acmicpc.net 문제 유형: 다익스트라 + dp 처음에는 포장할 도로를 조합하고, 이를 매번 다익스트라로 돌리려고 했다. 그리고 해당 결과물을 dp의 메모제이션 기법을 사용하려고 했으나, 어딘가 잘못됨을 느끼고 결국 구글링을해 풀이를 봤다. 문제의 핵심은, 1. 해당 노로 가는 경로를 '포장을 할 때' 와 '포장을 하지 않을때'로 구분 해야 한다. 2. 다익스트라의 최단거리 저..
알고리즘 2023. 7. 23. 18:14
1