량베개

27945번 슬슬 가지를 먹지 않으면 죽는다 G3 문제키위새는 가지와 사랑에 빠지면서 가지로 맛있는 요리를 하기 위해 1번부터 N번까지의 번호가 붙은 N개의 요리 학원에 다니기 시작했다. 각 요리 학원 사이에는 총 M개의 양방향 길이 있고, i번째 길에는 정확히 ti일에만 문을 여는 가지 디저트 노점이 있다. (ti는 모두 다르다.) 아직 가지 요리를 배우는 중인 키위새는 직접 가지 요리를 해 먹지는 못하다 보니 가지 부족증(hypomelitzemia)이 발생했다. 키위새는 이제 매일 노점에 들러 가지 디저트를 먹지 않으면 쓰러지게 된다. 심지어 기억력도 퇴화해 N−1개의 길만을 기억할 수 있게 되었다! 모든 요리 학원에 다닐 수 있도록 N−1개의 길을 골랐을 때, 키위새가 쓰러지는 날이 d일차라고 하자..

24461번 그래프의 줄기 G2 문제그래프에서 사이클이란, 한 정점에서 같은 정점까지, 반복되는 간선이 없으며, 길이가 0이 아닌 경로이다. 사이클이 존재하지 않는 그래프가 주어진다.우리는 이 그래프의 정점 중에서 연결된 간선이 하나인 정점을 가장자리 정점이라고 정의하자.이 그래프의 가장자리 정점을 동시에 없애는 행동을 반복하면서, 그래프가 일직선의 모양이 되면 남아있는 정점의 집합을 그래프의 줄기라고 정의하자. 단, 가장자리 정점의 개수가 둘 이하라면 그래프가 일직선 모양이라고 한다. 위 그림과 같은 그래프가 있다고 할 때, 아래와 같이 가장자리 정점과 연결된 간선을 빨간색으로 표시하면 아래와 같다. 빨간색 간선과 연결된 가장자리 정점의 연결을 끊으면 아래 그림과 같이 일직선 모양으로 연결된 그래프의 ..

2611번 자동차경주 G2 문제자동차 경주로는 의 예와 같이 표현된다. 화살표는 각 지점을 잇는 도로를 의미하며 모든 도로는 일방통행 도로로 화살표 방향으로만 움직일 수 있다. 자동차 경주의 코스는 1번 지점에서 출발하여 다시 1번 지점으로 되돌아오는 것이다. 단, 중간에는 1번 지점을 지나서는 안 된다. 경주로는 1번 지점을 제외한 어느 지점에서 출발하여도 1번 지점을 지나가지 않고서는 같은 지점으로 돌아올 수 없도록 되어 있다. 또한 1번 지점에서 다른 모든 지점으로 갈 수 있고, 다른 모든 지점에서 1번 지점으로 갈 수 있다. 각 도로에는 의 예와 같이 그 도로를 지날 때 얻는 점수가 있다. 1번 지점에서 출발하여 가장 많은 점수를 얻어 다시 1번 지점으로 돌아오는 팀이 우승을 하게 된다. 가장 많..

20010번 악덕 영주 혜유 G2 문제FT온라인 게임에서 치열한 경쟁을 통해 영주가 된 혜유는 퀘스트를 받았다. 퀘스트의 내용은 자신이 관리하고 있는 마을 사이에 교역로를 건설하여 마을 간 교류를 활성화시키는 것이다. 이때, 교역로는 양 방향으로 이동할 수 있으며, 서로 도달이 불가능한 마을이 없도록 교역로를 건설하여야 한다. 마음이 괘씸한 혜유는 돈을 최대한 적게 쓰면서 퀘스트를 달성하려고 한다. 폐유를 도와서 모든 마을과 마을을 최소한의 비용으로 연결하고 그 비용을 구해보자. 또한 혜유는 이때 마을과 마을을 이동하는 가장 최악의 비용이 얼마인지에 관심이 많다. 임의의 두 마을을 이동하는 최단 경로 중 비용이 가장 큰 경로의 비용도 구해보자.입력첫 번째 줄에는 마을의 수 N(1 ≤ N ≤ 1,000)과..