[백준 알고리즘] 1238번: 파티
March 22, 2021
https://www.acmicpc.net/problem/1238
문제
문제
N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다.
어느 날 이 N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 있고 i번째 길을 지나는데 Ti(1 ≤ Ti ≤ 100)의 시간을 소비한다.
각각의 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 한다. 하지만 이 학생들은 워낙 게을러서 최단 시간에 오고 가기를 원한다.
이 도로들은 단방향이기 때문에 아마 그들이 오고 가는 길이 다를지도 모른다. N명의 학생들 중 오고 가는데 가장 많은 시간을 소비하는 학생은 누구일지 구하여라.
입력
첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어온다. 시작점과 끝점이 같은 도로는 없으며, 시작점과 한 도시 A에서 다른 도시 B로 가는 도로의 개수는 최대 1개이다.
모든 학생들은 집에서 X에 갈수 있고, X에서 집으로 돌아올 수 있는 데이터만 입력으로 주어진다.
출력
첫 번째 줄에 N명의 학생들 중 오고 가는데 가장 오래 걸리는 학생의 소요시간을 출력한다.
풀이
평범한 다익스트라 문제처럼 보여서 일단 풀고 시작했지만, 계속 답이 안나와서 고민하던 중에 아 이거 단방향 그래프지..! 라는 생각이 들었다. 처음에 시도했던 방법은 모든 정점을 시작점으로 잡고 X까지 가장 큰 정점의 비용을 구한 뒤에 2를 곱해주는 것이었는데, 단방향 그래프이기 때문에 돌아갈 때 꼭 같은 길로 돌아간다는 보장이 없다. 그리고 이 힌트는 사실 문제에서 이미 주어졌다. 역시 이래서 문제를 잘 읽는 것이 중요하다..
다익스트라를 시뮬레이션하듯이 사용해서 돌아갈 때의 비용도 구해보는 것으로 쉽게 해결할 수 있었다. 이를 위해서 처음 간선 정보를 입력받을 떄 반대편 방향에 대한 정보를 미리 만들어두고 다익스트라 알고리즘을 파티장으로 갈 때 한 번, 돌아올 때 한 번, 총 2번 수행해서 가는 길과 오는 길의 비용의 합을 구했다. 그리고 이 중 가장 큰 값을 구해 출력했다.
코드
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <climits>
using namespace std;
struct Compare {
bool operator()(pair<int, int>& a, pair<int, int>& b) {
return a.second > b.second;
}
};
void dijkstra(int start, vector<vector<pair<int, int>>>& towns, vector<int>& dist) {
priority_queue<pair<int, int>, vector<pair<int, int>>, Compare> pq;
pq.push({ start, 0 });
dist[start] = 0;
while (!pq.empty()) {
int here = pq.top().first;
int hereCost = pq.top().second;
pq.pop();
if (dist[here] < hereCost) continue;
for (auto next : towns[here]) {
int there = next.first;
int thereCost = hereCost + next.second;
if (dist[there] > thereCost) {
dist[there] = thereCost;
pq.push({ there, thereCost });
}
}
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(NULL);
vector<vector<pair<int, int>>> wayToward(1001);
vector<vector<pair<int, int>>> wayBack(1001);
vector<int> distBack(1001, INT_MAX);
vector<int> distToward(1001, INT_MAX);
int N, M, X;
cin >> N >> M >> X;
for (int i = 0; i < M; i++) {
int here, there, cost;
cin >> here >> there >> cost;
wayToward[here].push_back({ there, cost });
wayBack[there].push_back({ here, cost });
}
dijkstra(X, wayToward, distToward);
dijkstra(X, wayBack, distBack);
int ans = 0;
for (int i = 1; i <= N; i++) {
ans = max(distToward[i] + distBack[i], ans);
}
cout << ans;
}
