백준알고리즘
거의 최단 거리
먼지의삶
2019. 9. 24. 23:26
https://www.acmicpc.net/problem/5719
5719번: 거의 최단 경로
문제 요즘 많은 자동차에서는 GPS 네비게이션 장비가 설치되어 있다. 네비게이션은 사용자가 입력한 출발점과 도착점 사이의 최단 경로를 검색해 준다. 하지만, 교통 상황을 고려하지 않고 최단 경로를 검색하는 경우에는 극심한 교통 정체를 경험할 수 있다. 상근이는 오직 자기 자신만 사용 가능한 네비게이션을 만들고 있다. 이 네비게이션은 절대로 최단 경로를 찾아주지 않는다. 항상 거의 최단 경로를 찾아준다. 거의 최단 경로란 최단 경로에 포함되지 않는 도로로만
www.acmicpc.net
|
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
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
|
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<utility>
#include<queue>
using namespace std;
int n, m, start, ending;
int map[501][501];
bool d[501];
bool d2[501];
bool dist[501];
int dos[501]; int dos2[501];
int minn = 987654321;
vector<int>ans;
vector<vector<pair<int,int>>> remov;
void bfs() {
queue<int> q;
q.push(start);
dist[start] = true;
while (!q.empty()) {
int st = q.front(); q.pop();
for (int i = 0; i < n; i++) {
if (map[st][i] != 0 && dist[i] == false) {
dist[i] = true;
dos[i] = dos[st] + map[st][i];
q.push(i);
}
else if (map[st][i] != 0 && dist[i] == true) {
if (dos[i] > dos[st] + map[st][i]) {
dist[i] = true;
dos[i] = dos[st] + map[st][i];
q.push(i);
}
}
}
}
}
void dfs(int x, int y, int cnt, vector<pair<int,int>>& gy) {
if (cnt > dos[ending]) return;
if (x == y) {
if (cnt == dos[ending]) {
remov.push_back(gy);
}
return;
}
else {
for (int i = 0; i < n; i++) {
if (map[x][i] != 0 && d[i] == false) {
d[i] = true;
gy.push_back({ x,i });
dfs(i, y, cnt + map[x][i],gy);
d[i] = false;
gy.pop_back();
}
}
}
}
void bfs2() {
queue<int> q;
q.push(start);
d2[start] = true;
while (!q.empty()) {
int st = q.front(); q.pop();
for (int i = 0; i < n; i++) {
if (map[st][i] != 0 && d2[i] == false) {
d2[i] = true;
dos2[i] = dos2[st] + map[st][i];
q.push(i);
}
else if (map[st][i] != 0 && d2[i] == true) {
if (dos2[i] > dos2[st] + map[st][i]) {
d2[i] = true;
dos2[i] = dos2[st] + map[st][i];
q.push(i);
}
}
}
}
if (dos2[ending] == 0) {
cout << -1 << '\n';
}
else {
cout << dos2[ending] << '\n';
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
while (true) {
int minn = 987654321;
cin >> n >> m;
if (n == 0 && m == 0) {
return 0;
}
cin >> start >> ending;
for (int i = 0; i < m; i++) {
int u, v, p;
cin >> u >> v >> p;
map[u][v] = p;
}
bfs();
minn = dos[ending];
vector<pair<int, int>>gy;
dfs(start, ending, 0, gy);
for (int i = 0; i < remov.size(); i++) {
for (int j = 0; j < remov[i].size(); j++) {
map[remov[i][j].first][remov[i][j].second] = 0;
}
}
bfs2();
int s, y;
memset(map, 0, sizeof(map));
memset(dos, 0, sizeof(dos));
memset(dos2, 0, sizeof(dos2));
memset(d, false, sizeof(d));
memset(d2, false, sizeof(d2));
memset(dist, false, sizeof(dist));
}
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter
|
나름 어려웠던문제가 아닐까싶다.
하지만 사실 로직자체는 굉장히 간단했다.
BFS로 최단거리 구하고 -> DFS로 최단거리에 해당하는 모든것들 경로를 저장하고 저장된 경로 제거하고
다시 BFS로 최단거리를 구하면 거의 최단 경로를 구할수있게된다.