문제 백준 1445번 풀이 우선 순위를 "쓰레기로 차있는 칸을 적게 지나가는 것"(A)을 높게 주고, "인접한 면을 적게 지나가는 것"(B)을 낮게 줍시다. 데이터를 두개로 관리하면서 다익스트라를 돌려주면 풀 수 있습니다. 그런데, 재미있는 풀이가 있어서 다뤄보려고 합니다. 위에서 우선 순위를 A를 높게, B를 낮게 줬고, A의 경우에 드는 가중치(비용)을 $ cost(A) $, B를 $ cost(B) $라고 둡시다. 각 정점까지 오는데의 비용을 아무리 $ cost(B) $를 합해도 $ cost(A) $가 안되도록 $ cost(A) $의 값을 설정합시다. 이 문제에서 정점의 개수가 많아봐야 2500개이므로, $ cost(B) = 1$, $ cost(A) = 2500 $으로 둡시다. 인접한 면을 지날 때는..

문제 백준 9694번 풀이 0번 정점(한신이)부터 최고의원을 만나기까지 친밀도의 합을 최소화하려면 최단 경로를 구하는 알고리즘을 사용하면 됩니다. 0번 정점을 시작 정점으로 잡아두고 다익스트라를 돌려주고, 각 정점을 갱신할 때마다 방문했던 정점들을 업데이트하면 쉽게 풀 수 있습니다. $ T $가 $ 100 $ 미만이고 $ N $이 $ 20 $ 이하이므로 플로이드-워셜(Floyd-Warshall)을 사용하더라도 $ O(TN^3) $에 풀릴 것 같습니다. 소스코드 #include using namespace std; typedef pair pii; int main() { cin.tie(0)->sync_with_stdio(0); cout.tie(0); int t; cin >> t; for (int i = 1;..

문제 백준 12930번 12930번: 두 가중치 0번 정점에서 1번 정점으로 가는 최단 경로의 비용을 출력한다. 0번에서 1번으로 갈 수 없는 경우에는 -1을 출력한다. www.acmicpc.net 풀이 조건이 복잡한 다익스트라입니다. priority queue에 cost, 현재 정점, 가중치 1의 합, 가중치 2의 합을 저장해두고 매번 갱신해주면 됩니다. 소스코드 #include using namespace std; typedef long long ll; typedef pair ppll; ll dist[21], graph[21][21][2]; vector _node[21]; int main() { cin.tie(0)->sync_with_stdio(0); int n; cin >> n; for (int t..