https://www.acmicpc.net/problem/2021 2021번: 최소 환승 경로 첫째 줄에 역의 개수 N(1≤N≤100,000), 노선의 개수 L(1≤L≤100,000)이 주어진다. 다음 L개의 줄에는 각 노선이 지나는 역이 순서대로 주어지며 각 줄의 마지막에는 -1이 주어진다. 마지막 줄에는 출발 www.acmicpc.net 디스코드방에서 추천받아서 풀어본 문제 일단 "최소" 라는 단어에서 다익스트라라는 감을 잡았다. 근데 같은 노선끼리는 이동거리를 0으로 해석해줄 수가 있어서, 사실상 같은 노선을 싹 뭉뚱그려서 하나의 무언가로 봐주는 과정이 필요하다 유니온 파인드 비슷한 느낌으로 노선 L개를 N+1번부터 각 노선당 한개의 노드를 할당해줬고, 각 역에서는 갈수있는 노선들을 이어줬다. 즉 ..

https://www.acmicpc.net/problem/9370 9370번: 미확인 도착지 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 www.acmicpc.net 다익스트라 문제인데 아니 이걸 왜이렇게 오래 뇌절을 쳤는지 모르겠다 엉엉엉 시작점 S에서 이동하는 서커스 예술가가 갈 목적지 후보 중에서 G-H간 도로를 건너 이동해야 하는 경로를 구하는 문제. 즉, 목적지 후보를 K라 할때, S-K 로 이동하는 최단경로가 S-G-H-K 이거나 S-H-G-K 이면 가능한 경우에 해당하고, S-K로 이동하는 최단경로의 길이가 S-G-H-K 이거나 S-H-G-K..

플래는 될줄 알았는데 웰노운이라서 골드1이란다 ㅠㅠ 세상 말세다 정말 엉엉엉 다익스트라 문제인데 그래프 가중치를 시간으로 생각해주면 된다. 저장된 최단거리가 최단시간에 도착하였을 경우의 시간이 되는 셈. 횡단보도 불이 들어올때까지 기다릴 수 있기 때문에, 당장은 가지 못하는 도로이더라도 처리를 해줘야 한다. while(dist >= ndist) ndist += M; if(dist > ndist)ndist += (ll)ceil((double)(dist-ndist)/M)*M; 아이디어는 대략 위와 같은데, 처음 K초에 지날수 있게 되는 다리는 K+M초, K+2M초, K+3M초 등등.... 에 다시 지날수 있게 되므로 첫번째 줄에서 M을 하나씩 더해가며 계산했지만 시간초과를 받았다. 그렇기때문에 둘 사이의 시..

다익스트라 알고리즘의 활용 문제 처음에는 각 면접장마다 다익스트라를 K번 돌리려고 생각했었는데, 이 경우에는 면접장의 개수가 많기 때문에 TLE를 받게 된다. 다익스트라를 한번만 돌리되 처음에 넣는 노드를 K개 넣어주어야 한다. 모든 면접장과 거리 0으로 연결되는 가상의 도시를 하나 만든다고 생각해도 무난하다. 다익스트라를 돌리고 난 뒤의 거리는 각 도시에서 가장 가까운 면접장으로 가는 거리값과 같으므로 이 거리 배열을 순회하면서 최대값을 구해주면 AC를 받을 수 있다. 이때 주의해야 할 점은 탐색방향이 반대가 되므로 방향그래프의 방향도 모두 뒤집어줘야한다는점? 이거때문에 좀 고생좀했습니다. 그리고 범위가 int범위를 넘어갈수있으니 long long 형을 사용해주도록 하자. #include #define..

[원석방 산하 폐수방] 1일차 셋 div 2 B번. 뇌절오지게했다. 이놈의다익스트라 구현만 1e9번 했는데 아직도 못외웠다는점에서 코더가 멍청하다는걸 바로알수있다... :blobsob: https://www.acmicpc.net/problem/20160 20160번: 야쿠르트 아줌마 야쿠르트 주세요 첫 줄에는 정점의 개수 V(1 ≤ V ≤ 10,000)와 도로의 개수 E(0 ≤ E ≤ 100,000)가 정수로 주어진다. 그 다음 E 줄에 걸쳐 각 도로를 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 이는 u 와 v(1 ≤ www.acmicpc.net 보고 다익스트라는 빠르게 떠올랐었다. 야쿠르트 아줌마 경로구하는것도 그냥 다익스트라를 많이 돌려주면 해결된다. 쬐끔 까다로웠던 부분이 야쿠르..

다익스트라 연습 (2) www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 각각의 좌표를 노드로, 각각의 좌표에 있는 도둑루피의 수를 가중치로 보자면 가중치합을 최소로 해서 (0,0) 에서 (n-1,n-1) 까지 이동하는 평범한 다익스트라 문제가 된다. 더보기 #include #define INF 123456789 #define st first #define nd second using namespace std; int arr[150][150]..