![]()
문제 풀이 다익스트라로 노드 간의 최단 거리를 구한다. 2가지 경로값 중 작은 값을 출력한다. 1 -> v1 -> v2 -> N 1 -> v2 -> v1 -> N 다익스트라는 1, v1, v2 총 3번만 실행하면 답을 구할 수 있다. 코드 #include #include #include using namespace std; vector edges; vector dists; void dijkstra(int start) { dists[start][start] = 0; priority_queue pq; pq.push(make_pair(0, start)); while (!pq.empty()) { int current_node = pq.top().second; int current_dist = (-1) * pq...
![]()
문제 풀이 다익스트라 알고리즘을 사용한다. 학생의 수 N만큼 각각의 학생이 X까지 가는 소요시간을 다익스트라로 계산하는 방법 혹은 역방향 간선을 사용하여 X까지의 소요시간이 최대인 학생을 찾는 방법 역방향 간선을 이용하는 방법은 2번만 다익스트라를 계산하면 되기에 속도차이가 크다. 코드 #include #include #include #include using namespace std; vector edges; vector reverse_edges; vector dists; vector reverse_dists; void dijkstra(int start) { dists[start][start] = 0; priority_queue q; q.push(make_pair(0, start)); while (!q..
