Hani_Levenshtein

https://www.acmicpc.net/problem/18223 18223번: 민준이와 마산 그리고 건우 입력의 첫 번째 줄에 정점의 개수 V와 간선의 개수 E, 그리고 건우가 위치한 정점 P가 주어진다. (2 ≤ V ≤ 5,000, 1 ≤ E ≤ 10,000, 1 ≤ P ≤ V) 두 번째 줄부터 E개의 줄에 걸쳐 각 간선의 정보 www.acmicpc.net 백준 소스코드 [C++] 18223 민준이와 마산 그리고 건우 #include #include #include #include #include using namespace std; #define MAX 987654321 int v, e, s, d, weight,via; vector adj[5000]; vector dijkstra(int src) ..

https://www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주�� www.acmicpc.net 백준 소스코드 [C++] 4485 녹색 옷 입은 애가 젤다지 #include #include #include #include #define MAX 987654321 using namespace std; int arr[127][127], n, cnt = 0; int dist[127][127]; pair pp, p[4] = { {1,0}, {0,1}, {-1,0}, {0,-1} ..

https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스� www.acmicpc.net 백준 소스코드 [C++] 11779 최소비용 구하기 2 #include #include #include #include #include using namespace std; int V,E,u,v,e,w,s,d; vector adj[1000]; vector dijkstra(int src) { priority_queue pq; vector dist(V, INT_MAX..

https://www.acmicpc.net/problem/2665 2665번: 미로만들기 첫 줄에는 한 줄에 들어가는 방의 수 n(1≤n≤50)이 주어지고, 다음 n개의 줄의 각 줄마다 0과 1이 이루어진 길이가 n인 수열이 주어진다. 0은 검은 방, 1은 흰 방을 나타낸다. www.acmicpc.net 백준 소스코드 [C++] 2665 미로만들기 #include #include #include #include #define MAX 987654321 using namespace std; int arr[52][52],n; int dist[52][52]; pair pp, p[4] = { {1,0}, {0,1}, {-1,0}, {0,-1} }; queue q; void bfs() { while (q.empty..

최단 경로 문제는 그래프에서 두 정점 사이의 가중치 합이 최소가 되는 경로의 길이를 찾는 문제입니다. 문제를 풀기 전에 아래의 상황을 고려해야 합니다. 1. 음수 가중치가 있는가 2. 시작점이 주어지는가 최단 경로 알고리즘에는 크게 다익스트라 알고리즘, 벨만-포드 알고리즘, 플로이드-와샬 알고리즘이 있습니다. 위에서 언급한 조건을 생각하여 어떤 알고리즘을 사용할지 선택해야하는데, 동일한 알고리즘이라도 구현 방식에 따라 알고리즘 성능이 좌우됩니다. 먼저, 1번을 고려해봅니다. 음수 가중치를 거쳐간다면 경로의 길이가 짧아지기 때문에 최단 경로를 결정할 때, 매력적인 선택지입니다. 그러나, 음수 가중치를 가진 경로가 사이클을 이루는 경우(한바퀴 돌았을 때의 합이 음수)가 있다면, -INF로 경로의 길이가 발산..

https://www.acmicpc.net/problem/6497 6497번: 전력난 성진이는 한 도시의 시장인데 거지라서 전력난에 끙끙댄다. 그래서 모든 길마다 원래 켜져 있던 가로등 중 일부를 소등하기로 하였다. 길의 가로등을 켜 두면 하루에 길의 미터 수만큼 돈이 들�� www.acmicpc.net 백준 소스코드 [C++] 6497 전력난 #include #include #include #include #include typedef long long ll; using namespace std; int Vertex, Edge, v, e, w; vectorE; struct DisjointSet { vector Parent, Rank; DisjointSet(int n) :Parent(n), Rank(n,..