1238번: 파티
문제 N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다. 어느 날 이 N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 있고 i번째 길을 지나는데 Ti(1 ≤ Ti ≤ 100)의 시간을 소비한다. 각각의 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 한다. 하지만 이 학생들은 워낙 게을러서 최단 시간에 오고 가기를 원한다. 이 도로들은 단방향이기 때
www.acmicpc.net
- 다익스트라 2회 수행
- 각 마을에서 출발해 X에 도착
- 각 간선의 방향을 반전시킨 후 X에서 출발하는 다익스트라 수행
- X에서 출발해 각 마을에 도착
- 두 거리의 합의 최댓값이 정답
- 각 마을에서 출발해 X에 도착
#include <iostream>
#include <limits.h>
#include <queue>
#include <algorithm>
using namespace std;
int N, M, X;
vector<pair<int, int>> graph1[1001], graph2[1001];
int dist1[1001], dist2[1001];
// 주어진 graph에 대해 다익스트라를 수행하고 dist에 거리 갱신
void dijkstra(vector<pair<int, int>> graph[], int dist[]) {
fill(dist + 1, dist + N + 1, INT_MAX / 2);
dist[X] = 0;
priority_queue<pair<int, int>> pq;
pq.push(make_pair(0, X));
while (!pq.empty()) {
int c = -pq.top().first, u = pq.top().second;
pq.pop();
if (dist[u] < c) {
continue;
}
for (auto v : graph[u]) {
if (dist[u] + v.second < dist[v.first]) {
dist[v.first] = dist[u] + v.second;
pq.push(make_pair(-dist[v.first], v.first));
}
}
}
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> N >> M >> X;
while (M--) {
int u, v, c;
cin >> u >> v >> c;
graph1[v].push_back(make_pair(u, c)); // 역방향 그래프
graph2[u].push_back(make_pair(v, c)); // 정방향 그래프
}
dijkstra(graph1, dist1); // X에서 출발하는 역방향 다익스트라 -> 각 마을에서 X로의 최단거리
dijkstra(graph2, dist2); // X에서 출발하는 정방향 다익스트라 -> X에서 각마을로의 최단거리
// 두 거리의 최댓값 갱신
int max_C = 0;
for (int u = 1; u <= N; ++u) {
max_C = max(max_C, dist1[u] + dist2[u]);
}
cout << max_C;
return 0;
}