백준 - 도망자 원숭이 (1602)

1. 문제 링크

도망자 원숭이

2. 풀이

우리가 유념해야할 사항은
'멍멍이는 최대로 괴롭힐 수 있는 위치에 존재한다' 입니다.
그렇기 때문에 멍멍이가 적게 괴롭힐 수 있는 순서대로 플로이드 와샬을 돌려야합니다.
(질문 검색에서 5년 전 해설글을 올려주신 kks227님 감사합니다)

1. 멍멍이 괴롭힘이 낮은 정점부터 갱신하도록 정렬

cin >> n >> m >> q;

for (int i = 1; i <= n; i++) {
	cin >> dogTeases[i];
	dogs.push_back({ dogTeases[i], i });
}

sort(dogs.begin(), dogs.end());

2. 거리와, 최대 괴롭힘 설정

int a, b, d;
while (m--) {
	cin >> a >> b >> d;

	dist[a][b] = dist[b][a] = d;
	maxTease[a][b] = maxTease[b][a] = max(dogTeases[a], dogTeases[b]);
}

3. 플로이드 와샬

for (int k = 0; k < n; k++) {
	int middle = dogs[k].second;

	for (int start = 1; start <= n; start++) {
		for (int end = 1; end <= n; end++) {
			// middle 지점을 거칠 때 멍멍이 최대 괴롭힘
			int middleTease = max(maxTease[start][middle], maxTease[middle][end]);
			// start -> end로  직진때 멍멍이 최대 괴롭힘(사실 직진이 아니긴 하지만..)
			int directTease = maxTease[start][end];

			// middle 경유 비용 + middle지점 거칠때 괴롭힘 vs 직진 경유 비용 + 직진일 때 괴롭힘
			if (dist[start][middle] + dist[middle][end] + middleTease < dist[start][end] + directTease) {
				dist[start][end] = dist[end][start] = dist[start][middle] + dist[middle][end];
				maxTease[start][end] = maxTease[end][start] = middleTease;
			}
		}
	}
}

3. 전체 코드

#include <bits/stdc++.h>

using namespace std;

const int INF = 0x3f3f3f3f;
int n, m, q;
int dist[501][501], maxTease[501][501];
int dogTeases[501];
vector<pair<int, int>> dogs;

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m >> q;

	for (int i = 1; i <= n; i++) {
		fill(dist[i] + 1, dist[i] + 1 + n, INF);
		dist[i][i] = 0;
		cin >> dogTeases[i];
		dogs.push_back({ dogTeases[i], i });
	}

	sort(dogs.begin(), dogs.end());

	int a, b, d;
	while (m--) {
		cin >> a >> b >> d;

		dist[a][b] = dist[b][a] = d;
		maxTease[a][b] = maxTease[b][a] = max(dogTeases[a], dogTeases[b]);
	}

	for (int k = 0; k < n; k++) {
		int middle = dogs[k].second;

		for (int start = 1; start <= n; start++) {
			for (int end = 1; end <= n; end++) {
				// middle 지점을 거칠 때 멍멍이 최대 괴롭힘
				int middleTease = max(maxTease[start][middle], maxTease[middle][end]);
				// start -> end로  직진때 멍멍이 최대 괴롭힘(사실 직진이 아니긴 하지만..)
				int directTease = maxTease[start][end];

				// middle 경유 비용 + middle지점 거칠때 괴롭힘 vs 직진 경유 비용 + 직진일 때 괴롭힘
				if (dist[start][middle] + dist[middle][end] + middleTease < dist[start][end] + directTease) {
					dist[start][end] = dist[end][start] = dist[start][middle] + dist[middle][end];
					maxTease[start][end] = maxTease[end][start] = middleTease;
				}
			}
		}
	}

	int s, t;
	while (q--) {
		cin >> s >> t;
		cout << (dist[s][t] == INF ? -1 : dist[s][t] + maxTease[s][t]) << '\n';
	}

	return 0;
}