SW Expert Academy
SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!
swexpertacademy.com
편의상 각 사원에 1번부터 N번까지 번호를 붙이도록 하자.
하루는 X번 사원의 강의실에서 간담회를 열기로 하였다.
각 사원들은 각자의 강의실에서
X번 사원의 강의실까지 갔다가 간담회를 마치고 돌아오려 한다.
이 때, 이동하는 경로는 최단 경로로 이동한다.
다만 문제는 각 강의실을 잇고 있는 M개의 길이 일방통행이라는 점이다.
결국, 그 강의실까지 가는 경로와 그 강의실에서
돌아오는 경로가 다를 수 밖에 없다.
각 길의 정보가 주어졌을 때, 간담회에 참석했다가
돌아오는데 소요되는 시간이 가장 긴 사원의 소요 시간을 알아내자.
<접근>
최단 경로로 이동하니까 다익스트라
다익스트라는
출발 노드와 모든 노드간의 최단 거리 탐색
"다른 강의실들 -> 간담회 장소 -> 다른 강의실들"
1. 간담회 장소 -> 다른 강의실들다익스트라가 적용 가능하다.
2. 다른 강의실들 -> 간담회 장소
강의실 하나 하나
다익스트라를 적용시켜야 한다.
시간 복잡도가 결국은
O(V * E log E)가 되어버린다.
어떻게 해야할까?
그래프의 간선을 방향을 반대로 하여
간담회 장소에서
다익스트라를 적용!!
<소스 코드>
|
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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
|
#include <iostream>
#include <vector>
#include <queue>
#include <limits.h>
using namespace std;
typedef pair<int, int> edge;
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int test;
cin >> test;
for (int t = 1; t <= test; t++)
{
vector<vector<edge>> graph;
vector<vector<edge>> r_graph;
vector<int> mdist;
vector<int> r_mdist;
vector<bool> visited;
vector<bool> r_visited;
priority_queue <edge, vector<edge>, greater<edge>> pq;
priority_queue <edge, vector<edge>, greater<edge>> r_pq;
int n, m, x;
cin >> n >> m >> x;
graph.resize(n + 1);
r_graph.resize(n + 1);
mdist.resize(n + 1);
r_mdist.resize(n + 1);
fill(mdist.begin(), mdist.end(), INT_MAX);
fill(r_mdist.begin(), r_mdist.end(), INT_MAX);
visited.resize(n + 1);
fill(visited.begin(), visited.end(), false);
r_visited.resize(n + 1);
fill(r_visited.begin(), r_visited.end(), false);
for (int i = 0; i < m; i++)
{
int s, e, t;
cin >> s >> e >> t;
graph[s].push_back({ e,t });
r_graph[e].push_back({ s,t });
}
pq.push(make_pair(0, x));
mdist[x] = 0;
while (!pq.empty())
{
edge current = pq.top();
pq.pop();
int c_v = current.second;
if (visited[c_v])
continue;
visited[c_v] = true;
for (int i = 0; i < graph[c_v].size(); i++)
{
edge tmp = graph[c_v][i];
int next = tmp.first;
int jikan = tmp.second;
if (mdist[next] > mdist[c_v] + jikan)
{
mdist[next] = jikan + mdist[c_v];
pq.push(make_pair(mdist[next], next));
}
}
}
r_pq.push(make_pair(0, x));
r_mdist[x] = 0;
while (!r_pq.empty())
{
edge current = r_pq.top();
r_pq.pop();
int c_v = current.second;
if (r_visited[c_v])
continue;
r_visited[c_v] = true;
for (int i = 0; i < r_graph[c_v].size(); i++)
{
edge tmp = r_graph[c_v][i];
int next = tmp.first;
int jikan = tmp.second;
if (r_mdist[next] > r_mdist[c_v] + jikan)
{
r_mdist[next] = jikan + r_mdist[c_v];
r_pq.push(make_pair(r_mdist[next], next));
}
}
}
int ans = 0;
for (int i = 1; i <= n; i++)
{
if (visited[i] && r_visited[i])
{
if (ans < (mdist[i] + r_mdist[i]))
{
ans = mdist[i] + r_mdist[i];
}
}
}
cout << '#' << t << ' ' << ans << '\n';
}
}
|
cs |