문제 URL : https://www.acmicpc.net/problem/16958
16958번: 텔레포트
2차원 평면 위에 N개의 도시가 있다. 일부 도시는 특별한 도시이다. (r1, c1)에 있는 도시에서 (r2, c2)에 있는 도시로 가는 이동 시간은 |r1 - r2| + |c1 - c2|와 같다. 만약, 두 도시가 특별한 도시라면, 텔
www.acmicpc.net
문제 접근법 :
n이 1000개라 플로이드 와샬로 풀수있을지 의아했는데 플로이드로 가능했고
시간을 줄이는 방법도 있으니 두개의 코드를 비교하면서 공부하시는것을 추천드립니다.
소스코드 :
첫번째 소스코드 :
|
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
|
#include <algorithm>
#include <vector>
#include <iostream>
#include <cmath>
using namespace std;
#define p pair<int,int>
int n, t,m;
vector<p> v,ans;
int teleport[1001];
int w[1001][1001];
void input() {
cin >> n >> t;
v.resize(n + 1);
for (int i = 1; i <= n; i++) {
int s, x, y;
cin >> s >> x >> y;
teleport[i] = s;
v[i].first = x;
v[i].second = y;
}
cin >> m;
for (int i = 0; i < m; i++) {
int x, y;
cin >> x >> y;
ans.push_back({ x,y });
}
}
void floyd() {
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
w[i][j] = min(w[i][j], w[i][k] + w[k][j]);
}
}
}
}
int Distance(int x1, int y1, int x2, int y2) {
return abs(x1 - x2) + abs(y1 - y2);
}
void solve() {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
int dist = Distance(v[i].first, v[i].second, v[j].first, v[j].second);
dist = (teleport[i] && teleport[j] ? min(dist, t) : dist);
w[i][j] = dist;
}
}
floyd();
for (int i = 0; i < m; i++) {
cout << w[ans[i].first][ans[i].second] << "\n";
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
input();
solve();
}
|
cs |
두번째 소스코드 :
|
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
|
#include <algorithm>
#include <vector>
#include <iostream>
#include <cmath>
using namespace std;
#define p pair<int,int>
int n, t,m;
vector<p> v,ans;
int teleport[1001];
int w[1001][1001];
void input() {
cin >> n >> t;
v.resize(n + 1);
for (int i = 1; i <= n; i++) {
int s, x, y;
cin >> s >> x >> y;
teleport[i] = s;
v[i].first = x;
v[i].second = y;
}
cin >> m;
for (int i = 0; i < m; i++) {
int x, y;
cin >> x >> y;
ans.push_back({ x,y });
}
}
int Distance(int x1, int y1, int x2, int y2) {
return abs(x1 - x2) + abs(y1 - y2);
}
void solve() {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
int dist = Distance(v[i].first, v[i].second, v[j].first, v[j].second);
w[i][j] = dist;
}
}
for (auto it : ans) {
int x = it.first;
int y = it.second;
int res = w[x][y];
int dist1 = 1e9;
int dist2 = 1e9;
for (int i = 1; i <= n; i++) {
if (teleport[i]) {
dist1 = min(dist1, w[x][i]);
dist2 = min(dist2, w[y][i]);
}
}
res = min(res, dist1 + dist2+t);
cout << res << "\n";
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
input();
solve();
}
|
cs |
궁금한점이나 지적 어떠한 질문이든 댓글은 언제나 환영입니다.
'백준' 카테고리의 다른 글
| 백준 12930 두 가중치 (0) | 2021.06.17 |
|---|---|
| 백준 1080 행렬 (0) | 2021.06.17 |
| 백준 2966 찍기 (0) | 2021.06.17 |
| 백준 2997 네 번째 수 (0) | 2021.06.17 |
| 백준 11003 최솟값 찾기 (0) | 2021.05.27 |