1865. 웜홀 벨만-포드를 응용한 문제이다. 특정 지점에서 다른 지점까지의 최단 거리를 구할 때, 다익스트라를 사용한다. 이때 음수 가중치가 존재한다면, 벨만-포드를 사용한다. 벨만-포드는 음수 사이클을 확인할 때도 사용한다. 모든 지점 간의 최단 거리를 구할 때는 플로이드-워셜을 사용한다. 그 외에, 최소 신장 트리(MST)를 구할 때는 크루스칼을 사용한다. 이 문제는 벨만-포드 알고리즘을 수행해 1번부터 다른 지점까지의 최단 거리를 구한 후, 마지막 N번째에서 음수 사이클을 확인하는 문제다. 음수 사이클을 판별하는 것이 중점이므로, 몇 번을 출발지로 할 지는 중요하지 않다. 단, 1번에서 도달 불가능한 부분에 음수 사이클이 존재할 수도 있으므로, 이 문제에선 ∞를 확인하는 부분을 없애줘야 한다. #..

11003. 최솟값 찾기 우선순위 큐를 활용한 슬라이딩 윈도우 문제이다. 최소힙을 유지하는 우선순위 큐를 구성하고, 인덱스와 값을 넣는다. 매번 top에서 원소를 확인할 때, 유효 기간이 지난(인덱스를 벗어나는) 원소를 pop한 후 출력하면 된다. 현재 원소보다 큰 유효기간이 지난 원소는 어차피 효력이 없으므로 문제되지 않는다. #include #include using namespace std; struct Elem { int idx; int data; friend bool operator B.data; } }; int main(int argc, char* argv[]) { ios_base::sync_with_s..

5597. 과제 안 내신 분..? #include using namespace std; int main(int argc, char* argv[]) { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); bool students[31] = {false}; for (int i = 0; i > id; students[id] = true; } for (int i = 1; i

11279. 최대 힙 우선순위 큐의 사용법을 묻는 간단한 문제였다. #include #include #include using namespace std; using uint = unsigned int; int main(int argc, char* argv[]) { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int N; priority_queue prque; ostringstream oss; cin >> N; while (N--) { uint num; cin >> num; if (num) { prque.emplace(num); } else if (prque.empty()) { oss