목록Algorithm/C++ (148)
cgy12306
메모리초과 때문에 이상하게 삽질했던 문제이다. 원인은 입력 받았을 때 path[to]=from으로 미리 처음에 경로를 세팅해뒀던 탓에 메모리 초과가 발생했다. // https://www.acmicpc.net/problem/11779 // 최소비용 구하기 2 #include #include #include #include using namespace std; int N, M, minCost[1002], INF = 999999999, path[1002]; vector ans; vector Edges; void dijkstra(int start) { priority_queue pq; minCost[start] = 0; pq.push({ 0, start }); while (!pq.empty()) { int cu..
// https://www.acmicpc.net/problem/10217 // KCM Travel #include #include #include #include #include using namespace std; int N, M, K, INF = 999999999; vector Edges; int minCost[102][10002]; void dijkstra(int start) { priority_queue pq; minCost[start][0] = 0; pq.push({ 0, 0, start }); while (!pq.empty()) { int current = get(pq.top()); int cost = get(pq.top()); int time = -get(pq.top()); pq.pop();..
// https://www.acmicpc.net/problem/10282 // 해킹 #include #include #include #include #include using namespace std; vector Edges; int minCost[10002], INF = 999999999; int n, d, c; void dijkstra(int start) { //for (int i = 1; i nextCost) { minCost[next] = nextCost; pq.push(make_pair(-nextCost, next)); } } } } int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int T; cin >> T; f..
// 메모리 초과 코드 #include #include #include #include #include using namespace std; int N; int parent[100002]; vector star; vector nebula; int Find(int x) { if (parent[x] == x) return x; return parent[x] = Find(parent[x]); } void Union(int a, int b) { a = Find(a); b = Find(b); if (a < b) parent[b] = a; else parent[a] = b; } void kruscal() { long long sum = 0; for (auto n : nebula) { int a = get(n); i..
// https://www.acmicpc.net/problem/9372 // 상근이의 여행 #include #include #include #include using namespace std; vector edges; int parent[1002]; int Find(int x) { if (parent[x] == x) return x; return parent[x] = Find(parent[x]); } void Union(int a, int b) { a = Find(a); b = Find(b); if (a < b) parent[b] = a; else parent[a] = b; } void kruskal() { int cnt = 0; for (auto e : edges) { int a = e.first; i..
// https://www.acmicpc.net/problem/1774 // 우주신과의 교감 #include #include #include #include #include using namespace std; int N, M; int parent[1002]; vector god; vector path; int Find(int x) { if (parent[x] == x) return x; return parent[x] = Find(parent[x]); } void Union(int a, int b) { a = Find(a); b = Find(b); if (a < b) parent[b] = a; else parent[a] = b; } void kruskal() { double sum = 0; for (au..
별의 입력 개수가 100개여서 2중 반복문을 통하여 각 별들의 거리를 구해준 다음 거리를 오름차순으로 정렬한뒤 kruskal을 이용해 별들의 거리를 구함 // https://www.acmicpc.net/problem/4386 // 별자리 만들기 #include #include #include #include #include using namespace std; int N; int parent[101]; vector star; vector nebula; int Find(int x) { if (parent[x] == x) return x; return parent[x] = Find(parent[x]); } void Union(int a, int b) { a = Find(a); b = Find(b); if (..
// https://www.acmicpc.net/problem/6497 // 전력난 #include #include #include #include #include using namespace std; int M, N, parent[200001], Msum; vector city; bool cmp(tuple a, tuple b) { return get(a) < get(b); } int Find(int x) { if (parent[x] == x) return x; return parent[x] = Find(parent[x]); } void Union(int a, int b) { a = Find(a); b = Find(b); if (a < b) parent[b] = a; else parent[a] = b; ..