그린푸딩

최단거리 역추적 문제 #include #include #include #include using namespace std; typedef pair ci; priority_queuepq; int main() { int n,m; cin>>n>>m; vectorarr(n+1,vector()); vectordist(n+1,100000000); vectorway(n+1,-1); int a,b,c; for(int i=0;i>a>>b>>c; arr[a].push_back({b,c}); } int f,e; cin>>f>>e; pq.push({0,f}); while(!pq.empty()){ int w=pq.top().first; int cur=pq.top().second; pq.pop(); if(w>dist[cur])c..

문제가 이해안되서 잘못 풀었는데 정점은 고정되어있고 턴마다 간선이 줄어드는것이다. 처음엔 간선들 사이에 여러개 트리가 있나? 했는데 그게 아니라 간선이 줄어드면서 똑같이 n개의 정점에 대하여 트리가 되는지 푸는 문제이다. 거기다 처음에 find()함수에 리턴을 = 이아니라 >m>>k; parent.assign(n+2,-1); vectorvisited; visited.assign(n+2,vector(n+2,false)); //간선 없애기 vectorpq; int x,y; for(int i=1;i>x>>y; pq.push_back({i,x,y}); visited[x][y]=true; } vectorans(k,0); int turn=0; //정점을 모두 사용한 트리군 트리가 되기만하면 되는게 아니라 //트리가..

모든 간선간의 거리를 구해서 작은순으로 정렬하고 이미 연결된 수 제외하고 n-v-1개까지 유니온시키기 좌표간 연결은 순번 을 부여해서 사용하면 된다. #include #include #include #include #include using namespace std; typedef tupletp; vectorparent; vectornum; double distance(double x1,double y1,double x2,double y2){ return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)); } int find(int node){ if(parent[node]n>>m; double x,y; parent.assign(n+1,-1); num.assign(n+1,{0,0}); f..

https://www.acmicpc.net/problem/2623 2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net #include #include #include using namespace std; int n, m; vectorindegree; vectorgraph; vectorarr; void tpsort() { queueq; for (int i = 1; i > n >> m; indegree.assign(n+1, 0); graph.assign(n + 1, vector()); int nu..