백준 15971 - 두 로봇(C++)

문제 링크입니다. https://www.acmicpc.net/problem/15971

15971번: 두 로봇

다익스트라 알고리즘을 통해 최단 경로를 찾은 뒤, 가장 긴 거리를 빼면 되는 문제입니다.

두 로봇이 통신하기 위한 최단 거리를 찾는 문제입니다.

 

로봇은 양쪽 전부 움직일 수도 있으며 한쪽만 움직일 수도 있습니다.

따라서 두 로봇을 움직여보면서 최단 거리를 찾아보면 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;
}

 

 

질문 및 조언은 댓글 남겨주세요