취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 4138번 문제인 Paper Route이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/4138 

주어진 문제의 상황은 newspaper office(0번 주소)와 각 신문을 배달할 주소, 그리고 Waterloo campus(100001번 주소로 잡을 것이다)를 노드와 그 사이에 알려진 이동시간로 이루어진 가중치 있는 그래프로 모델링할 수 있다.

모든 신문을 배달하기 전까지는 Waterloo campus를 방문할 수 없으므로, 위에서 모델링한 그래프에서 Waterloo campus 노드와 이와 연결된 에지를 빼고 생각하자. 이 때 주어진 그래프는 newpaper office(0번 노드)를 루트로 하는 트리로 생각할 수 있다. 그리고 모든 신문 배달이 종료되는 시점에 서있을 수 있는 노드들은 이 트리의 리프들과 같음을 알 수 있다.

각 리프를 마지막 노드로 신문 배달이 완료될 때까지의 걸리는 시간의 최솟값은 (트리의 모든 노드의 가중치*2)-(해당 리프와 루트 사이의 이동시간)로 계산할 수 있다는 것을 관찰하자. 또한 각 leaf에서 Waterloo campus까지 걸리는 최단시간은 Waterloo campus에서 각 address들까지 걸리는 최단시간을 구하는 것으로 계산할 수 있다. 이 값들은 dijkstra 알고리즘 등을 이용해 빠르게 구할 수 있다.

위에서 구한 값들을 이용하여, newspaper office에서 출발하여 각 leaf노드에서 신문을 배달을 마친 뒤 Waterloo campus까지 이동하는 각 경우 소요되는 최단시간을 구해 그중 최솟값을 출력하는 것으로 문제를 해결하자.

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int N;
vector<pair<int, int>> G[100002]; // 0: 회사, 100001: 학교
int distR[100002];
int mx, total;
vector<int> leaves;

void dfs(int cur, int par) {
	bool sgn = 0;
	for (auto& p : G[cur]) {
		int &nxt = p.first, &w = p.second;
		if (nxt == par || nxt == 100001) continue;
		distR[nxt] = distR[cur] + w;
		dfs(nxt, cur);
		sgn = 1;
	}

	if (!sgn) leaves.emplace_back(cur);
}

int distD[100002];
bool visited[100002];

void dijkstra() {
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
	pq.push(make_pair(0, 100001));
	while (!pq.empty()) {
		int cur = pq.top().second, d = pq.top().first; pq.pop();
		if (visited[cur]) continue;
		visited[cur] = 1;
		for (auto& p : G[cur]) {
			int& nxt = p.first, w = p.second;
			if (!visited[nxt] && (d + w < distD[nxt] || distD[nxt] == 0)) distD[nxt] = d + w, pq.push(make_pair(d + w, nxt));
		}
	}
}

int ans = 2000000007;

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

	cin >> N;
	for (int i = 0; i <= N; i++) {
		int c; cin >> c;
		G[i].emplace_back(make_pair(100001, c));
		G[100001].emplace_back(make_pair(i, c));
	}

	for (int i = 0; i < N; i++) {
		int x, y, c; cin >> x >> y >> c;
		G[x].emplace_back(make_pair(y, c));
		G[y].emplace_back(make_pair(x, c));
		total += c;
	}
	total *= 2;

	dfs(0, -1);
	dijkstra();

	for (auto& node : leaves) {
		ans = min(ans, total - distR[node] + distD[node]);
	}

	cout << ans;
}