너와 나의 스토리

문제: https://www.acmicpc.net/problem/4386 문제 풀이: mst를 사용한 문제 각 점들의 (x,y)값을 입력 받아 벡터에 저장하고 한 별에서 다른 별들로 갈 수 있는 모든 경로의 길이를 priority_queue에 저장 가장 짧은 길이를 가진 두 별을 팝해와서 이미 연결된 노드는 패스하고 아니면 연결해주고 그 길이를 res에 더해줌 최소만 연결하면 n-1개의 다리(?)가 생기므로 다 연결했으면 바로 break해주면 됨 소스 코드: typedef pair P; int n,p[101],cnt; double res; bool visit[101]; vector adj; priority_queue pq; int find(int x) { if (p[x] < 0) return x; ret..

문제: https://www.acmicpc.net/problem/1774 문제풀이: 거리를 모두 구해서 priority_queue에 넣음 mst 사용 주의1. double을 사용해야 한다. while문에서 cost를 int형으로 선언한걸 못 찾아서 계속 맞왜틀.... ㅠㅠ 하다가 겨우겨우 맞음 주의2. 미리 연결된 통로들이 항상 mst로 연결되었음을 보장할 수 없다. 즉, while문에서 if(cnt==n-m) break; 이런식으로 풀면 틀림 priority_queue 사용하는 것보다 vector에 거리 차 다 넣어 놓고 sorting 해서 풀면 시간이 절반으로 줄어든다. sort(pq.begin(), pq.end()); for(int i=0;i> n >> m; memset(p, -1, sizeof(p..

문제: https://www.acmicpc.net/problem/1922 문제 풀이: mst 사용 ㅎㅎ 소스 코드: typedef pair P; priority_queue pq; int n, m,cnt,p[1001],res; int find(int x) { if (p[x] > n >> m; memset(p, ..