https://www.acmicpc.net/problem/1238
1238번: 파티
첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어
www.acmicpc.net
문제 해결을 위한 과정
이 문제의 경우 역방향을 생각해야 하는 것이 가장 중요한 문제였습니다. 예제에서 파티가 열리는 장소가 2번이기 때문에 2를 다익스트라 알고리즘의 start로 넣어주면 2에서 다른 지점으로 가는 최소 거리를 구할 수 있고
역방향 그래프를 생성한 후 역방향의 그래프로 2를 다익스트라 알고리즘의 start로 넣어주면 다른 지점에서 2로 가는 최소 거리를 구할 수 있습니다.
소스코드 - python
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
|
import heapq
import sys
input = sys.stdin.readline
INF = int(1e9)
n, m, x = map(int, input().split())
graph = [[] for _ in range(1+n)]
graphR = [[] for _ in range(1+n)]
distance = [INF] * (n+1)
distanceR = [INF] * (n+1)
for _ in range(m):
a, b, c = map(int, input().split())
graph[a].append((b, c))
graphR[b].append((a, c))
def dijkstra(start):
q = []
heapq.heappush(q, (0, start))
distance[start] = 0
while q:
dist, now = heapq.heappop(q)
if distance[now] < dist:
continue
for i in graph[now]:
cost = dist + i[1]
if cost < distance[i[0]]:
distance[i[0]] = cost
heapq.heappush(q, (cost, i[0]))
def dijkstraR(start):
q = []
heapq.heappush(q, (0, start))
distanceR[start] = 0
while q:
dist, now = heapq.heappop(q)
if distanceR[now] < dist:
continue
for i in graphR[now]:
cost = dist + i[1]
if cost < distanceR[i[0]]:
distanceR[i[0]] = cost
heapq.heappush(q, (cost, i[0]))
dijkstra(x)
dijkstraR(x)
result = []
for i in range(1, n+1):
result.append(distance[i] + distanceR[i])
result.sort(reverse = True)
print(result[0])
|
cs |
소스코드 - c++-
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
|
#include <bits/stdc++.h>
#define MAX 1001
using namespace std;
vector<pair<int, int>> graph[MAX];
vector<pair<int, int>> graphR[MAX];
vector<int> result;
int d[MAX];
int dR[MAX];
int n, m, x;
void dijkstra(int start) {
priority_queue<pair<int, int>> pq;
pq.push(make_pair(0, start));
d[start] = 0;
while (!pq.empty()) {
int dist = -pq.top().first;
int now = pq.top().second;
pq.pop();
for (int i = 0; i < graph[now].size(); i++) {
int cost = dist + graph[now][i].second;
if (cost < d[graph[now][i].first]) {
d[graph[now][i].first] = cost;
pq.push(make_pair(-cost, graph[now][i].first));
}
}
}
}
void dijkstraR(int start) {
priority_queue<pair<int, int>> pq;
pq.push(make_pair(0, start));
dR[start] = 0;
while (!pq.empty()) {
int dist = -pq.top().first;
int now = pq.top().second;
pq.pop();
for (int i = 0; i < graphR[now].size(); i++) {
int cost = dist + graphR[now][i].second;
if (cost < dR[graphR[now][i].first]) {
dR[graphR[now][i].first] = cost;
pq.push(make_pair(-cost, graphR[now][i].first));
}
}
}
}
int main(void) {
scanf("%d %d %d", &n, &m, &x);
for (int i = 0; i < m; i++) {
int a, b, c;
cin >> a >> b >> c;
graph[a].push_back(make_pair(b, c));
graphR[b].push_back(make_pair(a, c));
}
int INF = (int)1e9;
fill(d, d + MAX, INF);
fill(dR, dR + MAX, INF);
dijkstra(x);
dijkstraR(x);
for (int i = 1; i < n+1; i++) {
result.push_back(d[i] + dR[i]);
}
sort(result.begin(), result.end(), greater<int>());
cout << result[0] << endl;
return 0;
}
|
cs |
'알고리즘 > 백준' 카테고리의 다른 글
| 백준 21608번: 상어 초등학교(Python) (0) | 2024.04.03 |
|---|---|
| 백준 21610번: 마법사 상어와 비바라기(Python) (0) | 2024.04.02 |
| 백준 1753번: 최단경로(Python, cpp) (0) | 2022.02.22 |
| 백준 12100번: 2048(Python, cpp) (0) | 2022.02.21 |
| 백준 16236번: 아기상어(Python, cpp) (0) | 2022.02.15 |