문제
풀이
들려야하는 두 점 을 지나면서 최단 경로를 구하는 문제.
두 점을 A, B라고 하면 최단 경로는 대략 다음과 같다.
- 1 - A - B - N
- 1 - B - A - N
그러므로 정점에서 정점까지의 최단경로를 전부 구하여 더하면 된다.
이를 위해 모든 쌍에서의 최단 경로를 구하는 알고리즘인 Floyd Warshall을 사용했다.
1
2
3
4
5
6
7
8
9
10
long long ans = min(adj[s][A] + adj[A][B] + adj[B][V - 1],
adj[s][B] + adj[B][A] + adj[A][V - 1]);
if (ans >= INT32_MAX)
{
cout << -1;
}
else
{
cout << ans;
}
증명
이에 관한 증명은 Floyd Warshall 증명과 비슷하다.
최단경로가 x를 경유할 때, 이 경로가 u에서 x로 가는 구간과 x에서 v로 가는 구간으로 나눌 수 있다.
- 이 두 부분 경로들은 최단 경로여야한다.
- 그렇지 않으면 최단경로라는 가정이 무너진다.
코드
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
int V, E;
int A, B;
long long adj[801][801];
void FD(int s)
{
for (int i = 0; i < V; i++)
adj[i][i] = 0;
for (int k = 0; k < V; k++)
{
for (int i = 0; i < V; i++)
{
for (int j = 0; j < V; j++)
{
adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j]);
}
}
}
long long ans = min(adj[s][A] + adj[A][B] + adj[B][V - 1], adj[s][B] + adj[B][A] + adj[A][V - 1]);
if (ans >= INT32_MAX)
{
cout << -1;
}
else
{
cout << ans;
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> V >> E;
for (int i = 0; i < V; i++)
{
for (int j = 0; j < V; j++)
{
adj[i][j] = INT32_MAX;
}
}
for (int i = 0; i < E; i++)
{
int a, b, c;
cin >> a >> b >> c;
adj[a - 1][b - 1] = c;
adj[b - 1][a - 1] = c;
}
cin >> A >> B;
A--;
B--;
FD(0);
}