전체 글 썸네일형 리스트형 UVaOJ)12878 Flowery Trails 문제:https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4743 그래프에서 0번 정점에서 n-1번 정점으로의 여러경로의 최단거리에 속한 간선들의 가중치의 합을 구하는 문제이다. 한 정점에서 한 정점으로의 최단거리가 유일하다면 경로의 가중치의 합을 구하는건 그렇게 어렵지 않게 풀 수 있다. 하지만 최단거리가 여러가지 경로가 있다면 다익스트라를 이용할 시 그걸 구하는 시간만해도 꽤 오랜 시간이 걸릴 수 있다. 처음 문제를 접근할 때 다익스트라를 돌리며 일일이 경로를 다 저장하여 역추적을 하여 tle를 받게되었다. 하지만 잘 생각해본다면 다익스트라(혹은 spfa) 두번의 전처리로 문제를 해.. 더보기 BOJ)9023 연습시즌 문제: icpc.me/9023 연습 일정에 맞춰서 경기장이나 호텔을 빌려야 할 때 두 팀이 지불해야하는 비용의 합의 최솟값을 구하는 문제이다. 다이나믹 프로그래밍을 이용하여 해결해줄 수 있는데 점화식을 세울 때 주의할 점은 두 팀 다 쉬는날이 없게해야한다. (무조건 손해) dp테이블을 dp[x][y][bx][by] (x번째 경기 y번째 경기를 진행해야되고 bx,by는 이전에 호텔에 묶었는지 여부 )로 세워준다음에 점화식을 세워주면 된다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950#include #include #include #include #define INF 1e9using nam.. 더보기 BOJ)13309 트리 문제:icpc.me/13309 트리에서 두 가지 쿼리를 처리하는 문제이다. 첫번 째 쿼리는 두 정점이 같은 컴포넌트에 존재하는지 여부이고 두번 째 쿼리는 두 정점이 같은 컴포넌트에 존재하는지 여부를 물음과 동시에 존재할 경우 두 정점 x,y 중 x와 x의 부모의 간선을 단절 존재하지 않을 경우 y와 y의 부모의 간선을 단절 시키는 쿼리이다. 오래 생각하다가 못 풀겠어서 풀이를 봤는데 재밌는 문제였다. 우선 루트에서 DFS를 돌면서 정점들의 번호를 방문하는 순서대로 새롭게 매겨준다. 이렇게 하면 어떤 정점 A의 자식들은 모두 A보다 큰 번호를 연속적으로 가지게 된다. 이걸 이용하여 정점 A부터 A의 자식들까지 범위를 저장해놓고 있을 수 있다. 그렇다면 두 정점이 같은 컴포넌트인지 확인하는 경우를 올라갈 수.. 더보기 이전 1 ··· 28 29 30 31 32 33 34 ··· 118 다음