Notice
Recent Posts
Recent Comments
Link
알고리즘 모음(C++)
백준 15971 - 두 로봇(C++) 본문
문제 링크입니다. https://www.acmicpc.net/problem/15971
15971번: 두 로봇
입력에서 두 번째 줄에 주어지는 방번호는 1과 2, 세 번째 줄에 주어지는 방 번호는 2와 3, …, i번째 줄에 주어지는 방 번호는 i-1과 i, …, N번째 줄에 주어지는 방 번호는 N-1과 N이다 (아래 입력과
www.acmicpc.net
다익스트라 알고리즘을 통해 최단 경로를 찾은 뒤, 가장 긴 거리를 빼면 되는 문제입니다.
두 로봇이 통신하기 위한 최단 거리를 찾는 문제입니다.
로봇은 양쪽 전부 움직일 수도 있으며 한쪽만 움직일 수도 있습니다.
따라서 두 로봇을 움직여보면서 최단 거리를 찾아보면 100000이 넘은 N의 범위 때문에 시간 초과가 생길 수 있습니다.
그래서 다익스트라 알고리즘을 사용해야 합니다.
다익스트라 알고리즘을 사용해 두 로봇 사이의 최소 거리를 찾아줍니다.
로봇들은 서로 연결된 노드에서 통신할 수 있습니다.
따라서 노드 사이의 거리가 최대인 지점만 피해 로봇을 움직인다면 최소 거리가 나올 수 있음을 생각할 수 있습니다.
자세한 것은 코드를 참고해주세요
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <cstring>
#include <string>
#define INF 987654321
#define P pair<int,int>
#define PP pair<pair<int,int>,int>
using namespace std;
int N, start, finish;
int Distance[100001];
vector<P> connect[100001];
priority_queue < P, vector<P> > q;
int Max[100001];
void reset_distance() {
for (int i = 1; i <= N; i++) {
Distance[i] = INF;
}
}
void dijstra() {
Distance[start] = 0;
q.push({ -Distance[start], start });
while (!q.empty()) {
int cost = -q.top().first;
int X = q.top().second;
q.pop();
for (int i = 0; i < connect[X].size(); i++) {
int xx = connect[X][i].first;
int Cost = connect[X][i].second;
if (Distance[xx] > cost + Cost) {
Distance[xx] = cost + Cost;
Max[xx] = max(Max[X], Cost);
q.push({ -Distance[xx], xx });
}
}
}
}
void solve() {
reset_distance();
dijstra();
cout << Distance[finish] - Max[finish];
}
int main() {
cin.tie(0);
cout.tie(0);
cin >> N >> start >> finish;
for (int i = 1; i < N; i++) {
int x, y, cost;
cin >> x >> y >> cost;
connect[x].push_back({ y,cost });
connect[y].push_back({ x,cost });
}
solve();
return 0;
}
질문 및 조언은 댓글 남겨주세요
'백준' 카테고리의 다른 글
백준 14864 - 줄서기(C++) (0) | 2022.07.01 |
---|---|
백준 15972 - 물탱크(C++) (0) | 2022.06.30 |
백준 25214 - 크림 파스타(C++) (0) | 2022.06.29 |
백준 25208 - 새벽의 탐정 게임(C++) (0) | 2022.06.28 |
백준 3187 - 양치기 꿍(C++) (0) | 2022.05.21 |