목록분류 전체보기 (370)
cgy12306
// https://www.acmicpc.net/problem/16398 // 행성 연결 #include #include #include #include using namespace std; long long N, parent[1002], map[1002][1002]; vector Edges; int Find(int x) { if (parent[x] == x) return x; else 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() { long long sum = 0; for (..
초기에 발전소끼리 Union 해준뒤 kruskal 알고리즘을 돌리면 쉽게 풀리는 문제이다. // https://www.acmicpc.net/problem/10423 // 전기가 부족해 #include #include #include #include using namespace std; int N, M, K; int parent[1002]; vector city; vector powerPlant; int Find(int x) { if (parent[x] == x) return x; else 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 ..
메모리초과 때문에 이상하게 삽질했던 문제이다. 원인은 입력 받았을 때 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..