데이크스트라

문제 링크https://www.acmicpc.net/problem/33531 문제Every student knows the practice: after having had one too many drinks in the \PUB, you will go to the Doner Shop to treat yourself with some comfort food.But experience tells you that you and your friends will not recall the way to the Doner Shop when you are drunk. Besides there are a lot of Doner Shops in the city. Therefore you decide to write a p..

문제 링크https://www.acmicpc.net/problem/31502  문제토카는 어쩌다 마주친 아름다운 한별 선배에게 마음을 빼앗겨 버리고 말았다! 말을 걸고 싶었지만 그럴 자신이 없었던 토카는 한별 선배에게 말을 걸 만한 명분을 찾기 시작했다. 평소에 만화를 많이 읽던 토카는 그 명분을 만들 방법을 한 만화책에서 찾아냈다! 만화 속 남자 주인공과 여자 주인공이 등굣길에 벚꽃 아래에서 서로 부딪혔던 사건을 계기로 친해졌다는 내용을 보고 직접 따라 하기로 결심했다.토카네 동네에는 벚나무가 없기 때문에 대신 은행나무가 있는 곳에서 시도하고자 한다. 토카네 동네는 1부터 N까지의 번호가 붙은 N개의 은행나무와 양 끝에 은행나무가 심어진 M개의 도로로 구성되어 있다. 모든 도로는 양방향 이동이 가능하며..

문제 링크https://www.acmicpc.net/problem/32197 문제지하철의 전기를 공급받는 방식(급전 방식)은 직류와 교류로 구분된다. 열차 운행 중 급전 방식이 바뀌게 되면 잠시 전력 공급이 중단된다. 이러한 현상을 절연이라 부른다. 열차 탑승객의 만족도는 절연이 적게 발생할수록 높아진다.서울특별시에는 N개의 지하철역이 있고, 두 역을 직접 잇는 선로 M개가 설치되어 있다. 각 역에는 1부터 N번까지의 번호가, 선로에는 1부터 M번까지의 번호가 붙어있다. 설치되어 있는 선로만으로 임의의 두 역 사이를 이동할 수 있다. 각 선로는 직류 또는 교류 중 하나의 방식으로 전기를 공급하며 양방향으로 통행할 수 있다.열차는 어떤 역과 이어진 선로를 통해 다른 역으로 이동하는 과정을 몇 번이든 반복할..

문제 링크https://www.acmicpc.net/problem/32770 문제세종이는 오늘따라 집이 너무 가고 싶어서 외출을 하기로 했다. 학교와 집을 왕복할 때는 버스를 이용하는데, 귀교 시간에 맞춰 돌아오기 위해서는 학교에서 집으로 갔다가, 학교로 다시 돌아오는 데 걸리는 시간을 알아야 한다.세종에는 E개의 버스 노선이 있다. 각 노선의 버스는 정해진 출발 정류장에서 도착 정류장으로만 이동하며, 반대 방향으로는 이동하지 않는다. 단, 세종이는 정말 운이 좋아서 정류장에 도착하면 언제나 바로 원하는 버스에 탈 수 있다. (와! 정말 부럽다)최대한 오래 집에 있고 싶어 하는 세종이를 위해 학교에서 집으로 다시 집에서 학교로 돌아오는데 걸리는 최소 시간을 구해주자. 입력첫째 줄에 버스 노선의 수 E가 ..

문제 링크 https://www.acmicpc.net/problem/31230 31230번: 모비스터디 첫 번째 테스트 케이스에 대한 그림이다. 이 테스트 케이스에는 $1 → 7 → 2 → 6$ 경로와 $1 → 4 → 5 → 2 → 6$ 경로 총 2개의 최단 경로가 존재하며, 최단 경로 위에 존재하는 도시는 $1$, $2$, $4$, $5 www.acmicpc.net 문제 현대모비스는 글로벌 자동차 부품 기업으로 자율주행, 커넥티비티, 전동화 분야에 역량을 집중해 스마트 모빌리티 시대를 선도하고 있습니다. 현대모비스는 앞으로 미래 모빌리티 산업에서 소프트웨어와 하드웨어를 결합한 차별화된 모빌리티 솔루션을 제공하는 선도기업으로 도약하기 위해 노력하고 있으며, 이러한 연구개발과 생산능력 등 핵심역량을 바탕으..

문제 링크 https://www.acmicpc.net/problem/30985 30985번: 직장인 파댕이의 사회생활 첫째 줄에 방의 수 $N (2 \leq N \leq 100,000)$과 복도의 수 $M (1 \leq M \leq 300,000)$, 건물의 층수 $K (2 \leq K \leq 200,000)$가 공백으로 구분되어 주어진다. 다음 줄부터 $M$개의 줄에 걸쳐 세 정수 $u, v, c$가 공 www.acmicpc.net 문제 파댕이는 중견기업 회사에서 직장인으로 일하고 있다. 사장님이 직장인 파댕이를 무척 아끼기 때문에, 파댕이는 사장실에 찾아가 사장님께 인사를 하려고 한다. 직장인 파댕이의 회사가 있는 건물은 K층으로 구성되어 있는데 각 층은 방과 복도로 구성되어 있다. 복도를 통해 방..

문제 링크 https://www.acmicpc.net/problem/30974 30974번: What's your ETA? 첫 번째 줄에는 버스 정류장의 개수 $N$과 임의의 두 버스 정류장 사이를 잇는 양방향 도로의 개수 $M$이 공백으로 구분되어 주어진다. $(2 ≤ N ≤ 400\,000; 1 ≤ M ≤ 1\,000\,000)$ 두 번째 줄에는 각 버 www.acmicpc.net 문제 진주 나들이를 온 보선이는 버스를 타고 미리 예약해놓은 진양호 전망대에 가기 위해 가까운 버스 정류장에 도착했다. 그런데 이상하게 버스정보안내단말기에 단 한 대의 도착 정보도 표시되지 않았다. 당황한 보선이가 여기저기 알아보던 도중, 보선이의 대학 동기인 준희로부터 문자 한 통이 왔다. 맛이 어때? 알고 보니 이는 준..

문제 링크 https://www.acmicpc.net/problem/25636 25636번: 소방차 ANA 도시는 $N$개의 교차로와, $M$개의 양방향 도로로 이루어져 있고, 교차로는 $1$번부터 $N$번까지 번호가 매겨져 있다. $S$번 교차로에는 ANA 도시의 유일한 소방서가 위치하는데, 무겸이는 이곳에 www.acmicpc.net 문제 ANA 도시는 N개의 교차로와, M개의 양방향 도로로 이루어져 있고, 교차로는 1번부터 N번까지 번호가 매겨져 있다. S번 교차로에는 ANA 도시의 유일한 소방서가 위치하는데, 무겸이는 이곳에서 소방차 운전 기사로 일하고 있다. 무겸이는 소방차를 타고 화재가 발생한 교차로에 출동해서 화재를 진압한다. 소방차에는 물을 담을 수 있는 물탱크가 있어서 이곳에 담은 물을 ..