(BOJ) 15971 두 로봇

문제: https://www.acmicpc.net/problem/15971

 

방법 1:

 

1. 다익스트라 돌려서 a에서 b까지 최단 경로를 찾는다. (변수명: a->src, b->dest)

2. 두 로봇은 한 칸 떨어졌을때 통신 가능하다

• 최단 경로 중 edge 하나를 뺀 것과 동일
• 끝 점부터 최단 경로를 추적하면서 제일 weight이 큰 edge를 찾아서 
• 최단 경로 cost - maxW을 결과로 출력한다.

 

소스코드:

#include <iostream>
#include <string.h>
#include <algorithm>
#include <queue>
#include <vector>
#define inf 1000000000
using namespace std;

typedef long long ll;
typedef pair<int, int> P;
int n,m,src,dest;
int dist[100002],maxW;
bool visit[100002];
vector<vector<P>> adj;
priority_queue<P> pq;
void dijkstra() {
	fill(dist, dist + n + 1, inf);
	dist[src] = 0;
	pq.push({ 0,src });
	while (!pq.empty()) {
		int cur;
		do {
			cur = pq.top().second;
			pq.pop();
		} while (!pq.empty() && visit[cur]);
		if (visit[cur]||cur==dest) break;
		visit[cur] = true;

		for (auto tmp: adj[cur]) {
			int next = tmp.second;
			if (dist[next] > dist[cur] + tmp.first) {
				dist[next] =dist[cur] + tmp.first;
				pq.push({ dist[next],next });
			}
		}
	}
}

// 최단 경로 중 가장 weight이 큰 부분을 찾는다. 
void findPath() {
	memset(visit, 0, sizeof(visit));
	queue<int> q;
	q.push(dest);
	visit[dest] = true;
	
	while (!q.empty()) {
		int cur = q.front();
		q.pop();

		for (auto i : adj[cur]) {
			int next = i.second;
			if (visit[next]) continue;
			if (dist[next] == dist[cur] - i.first) {
				maxW = max(maxW, i.first);
				visit[cur] = true;
				q.push(next);
			}
		}
	}
	
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n >> src >> dest;

	adj.resize(n + 1);

	for (int i = 0; i < n - 1; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		adj[a].push_back({ c,b });
		adj[b].push_back({ c,a });
	}
	dijkstra();
	findPath();
	cout<<dist[dest]-maxW<<'\n';
	return 0;
}

 

 

방법 2:

각 로봇의 처음 위치를 a, b라고 할 때

1. a를 시작으로 다익스트라 돌림

2. b를 시작으로 bfs 돌리는데

(현재 위치까지의 cost)+(다음 갈 곳까지 a가 올 cost)가 최소인 것을 답으로 계속 갱신해주기 

 

*주의:

1. 각 두 로봇이 처음 위치한 곳이 동일한 곳일 때

2. n이 1일 때

 

dist[0][n] -> a에서 출발

dist[1][n] -> b에서 출발

 

소스 코드:

int n, a, b;
long long dist[2][100001];
bool visit[100001];
typedef pair<int, int> P;
vector<vector<P>> adj;

void di(int t,int start) {
	priority_queue<P, vector<P>, greater<P>> pq;
	dist[t][start] = 0;
	pq.push({ 0,start });

	while (!pq.empty()) {
		int cur;
		do {
			cur = pq.top().second;
			pq.pop();
		} while (!pq.empty() && visit[cur]);
		if (visit[cur]) break;
		visit[cur] = true;

		for (auto i : adj[cur]) {
			int next = i.second;
			if (dist[t][next] > dist[t][cur] + i.first) {
				dist[t][next] = dist[t][cur] + i.first;
				pq.push({ dist[t][next],i.second });
			}
		}
	}
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);
	
	cin >> n >> a >> b;

	fill(dist[0], dist[0] + n + 1, inf);
	fill(dist[1], dist[1] + n + 1, inf);
	adj.resize(n + 1);
	for (int i = 1; i < n; i++) {
		int q, w, e;
		cin >> q >> w >> e;
		adj[q].push_back({ e,w });
		adj[w].push_back({ e,q });
	}
	if (n == 1 || a == b) {
		cout << "0\n";
		return 0;
	}
	di(0, a);

	memset(visit, false, sizeof(visit));
	queue<int> q;
	q.push(b);
	dist[1][b] = 0;
	visit[b] = true;
	long long res = inf;
	while (!q.empty()) {
		int cur = q.front();
		q.pop();

		for (auto i : adj[cur]) {
			int next = i.second;
			if (visit[next]) continue;
			visit[next] = true;
			res = min(res, dist[1][cur] + dist[0][next]);
			if (dist[1][next] > dist[1][cur] + i.first) {
				dist[1][next] = dist[1][cur] + i.first;
				q.push(next);
			}
		}
	}
	cout << res << '\n';
	return 0;
}