lastknight00

문제 링크 : [백준]무엇을 아느냐가 아니라 누구를 아느냐가 문제다(9694) 문제 설명 0번 노드에서 N-1번 노드까지의 최단거리를 가는 경로를 구하세요. 입력 T(테스트 케이스, 1 < T < 100) N(엣지의 갯수, N

문제 링크 : [백준]민준이와 마산 그리고 건우(18223) 문제 설명 1번 노드에서 V번까지 가는 최단거리가 1번에서 P번 노드를 거쳐 V번 노드까지 가는 최단거리보다 작거나 같은지 판별하세요. 입력 V(노드의 갯수, 1 1로 가는 최단거리 + P -> V로 가는 최단거리를 더하면 됩니다. 시간복잡도 O(M * logM) 코드 #include #include #include #include #include #define N 5001 using namespace std; typedef pairP; int n,m,p,a,b,c,d[N],e[N],w[N]; vectorv[N]; priority_queueq; void r(int s,int d[]){ memset(w,0,sizeof(w)); q.push({0,..

문제 링크 : [백준]브리징 시그널(3066) 문제 설명 LIS문제입니다. 입력 T(테스트 케이스 갯수) N(포트의 갯수, 1 t; while(t--){ v.clear(); cin>>n; while(n--){ cin>>x; if(v.empty()||v.back()

문제 링크 : [백준]전구(2550) 문제 설명 스위치와 매핑되는 전구들의 입력이 주어집니다. 스위치를 눌러 전구를 켜는데, 선이 교차되는 경우에는 켜지지 않습니다. 최대한 많은 전구를 켤 때의 갯수와 그때 눌러야 할 스위치 번호를 구하세요. 입력 N(전구의 갯수, 1

문제 링크 : [백준]간선 이어가기 2(14284) 문제 설명 연결이 없는 노드 N개가 주어집니다. 그 이후에 M개의 무방향 가중치 엣지가 주어집니다. 출발지 S와 도착지 T가 주어지면, 이전에 주어진 간선들의 순서를 원하는대로 바꾸고 순서대로 하나씩 간선을 이어나가다가 S와 T가 이어지는 순간 작업을 멈춥니다. 이때 이은 간선들의 가중치의 합의 최소값을 구하세요. 입력 N(노드의 갯수, 1 a>>b>>c; v[a].push_back({c,b}); v[b].push_back({c,a}); } cin>>a>>b; q.push({0,a}); while(!q.empty()){ P x=q.top();q.pop(); if(d[x.second])continue; d[x.second]=1; if(x.second==b..

문제 링크 : [백준]소가 길을 건너간 이유 7(14461) 문제 설명 N * N 행렬이 주어지고, 각 칸에는 풀의 양이 주어집니다. 소는 (1,1)에서 출발하여, (N,N)까지 이동해야 합니다. 각 칸을 이동 할 때는 T초가 걸리며, 소가 세칸을 이동한 후에는 그 칸의 풀을 먹어야 합니다. 소가 도착하는데 걸리는 최소 시간을 구하세요. 입력 N(행렬의 크기, 1

문제 링크 : [백준]백도어(17396) 문제 설명 N개의 노드와 M개의 비용을 포함한 엣지 정보가 주어집니다. 또한 각 노드를 경우할 수 있는지 여부도 주어집니다.(N-1번 노드는 1이어도 방문 가능합니다.) 0번 노드에서 시작하여 N-1번 노드까지 가는 최단 경로를 구하세요. 입력 N(노드의 갯수, 1 d[i]; d[n-1]=0; while(m--){ cin>>a>>b>>c; v[a].push_back({c,b}); v[b].push_back({c,a}); } q.push({0,0}); while(!q.empty()){ P x=q.top();q.pop(); if(e[x.second])continue; e[x.second]=1; if(x.second==n-1){ cout

문제 링크 : [백준]소수마을(14431) 문제 설명 소수마을과 A마을, N개의 마을들의 좌표가 주어집니다. 소수마을에서 A마을까지 이동하려고 하는데, 이동 할 때는, 이동거리가 소수인 경우에만 이동 할 수 있습니다. 이동거리는 두 마을간의 이동 거리이며, 소수점은 버립니다. 소수마을에서 A마을까지의 최단거리를 구하세요. 입력 Px Py Ax Ay(소수마을의 좌표, 마을의 좌표) N(마을의 갯수, 1