[C++/16958] 텔레포트

---

⛔ 단순히 기록용 입니다... 어떻게 풀었는가 생각도 다시 해보고 그러니까 아마도 도움은 안되실 것 같습니다.

---

플로이드 와샬로 풀었지만, 이동할 수 있는 도시를 전부 계산한 후에 텔레포트로 이동이 가능한 곳에서 다시 이동이 가능한지 파악하면 문제를 해결할 수 있을 것이라고 본다.

근데 문제 해결할 때는 플로이드 와샬로 문제를 해결했는데, 생각해보면 N 3제곱이기 때문에 10억이라는 값이 나와서 시간초과가 되는게 당연했는데 문제가 풀렸다? 이유는 단순 계산은 시간을 넉넉히 준다는 것이라는데 이유는 정확히 모르겠다. 아마 시간초과 됐으면 텔레포트되는 곳을 찾아서 문제를 해결했을 것 같습니다. 아래는 정답 코드입니다.

#include<iostream>

#define MAX 1010
using namespace std;

struct info{
	int special;
	int x;
	int y;
};

info infos[MAX];
int n,m,s,t,x,y,timeTable[MAX][MAX];

void init() {
	
	cin >> n >> t;
	
	for(int i = 0; i < n; i++){
		cin >> s >> x >> y;
		infos[i+1] = {s,x,y};
	}
	
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= n; j++){
			if(i == j) continue;
			
			timeTable[i][j] = 987654321;
		}
	}
	
}

int calcDist(int x, int y, int x2, int y2){
	return abs(x2 - x) + abs(y2 - y);
}

void setting() {
	
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= n; j++){
			
			if(i == j) continue;
			
			if(infos[i].special && infos[j].special){
				timeTable[i][j] = min(t, calcDist(infos[i].x, infos[i].y, infos[j].x, infos[j].y));
			} else{
				timeTable[i][j] = calcDist(infos[i].x, infos[i].y, infos[j].x, infos[j].y);
			}
			
		}
	}
	
}

void floyd() {
	
	for(int via = 1; via <= n; via++){
		for(int from = 1; from <= n; from++){
			if(via == from) continue;
			for(int to = 1; to <= n; to++){
				if(from == to) continue;
				timeTable[from][to] = min(timeTable[from][to], timeTable[from][via] + timeTable[via][to]);
			}
		}
	}
	
	
}

void solve() {
	
	cin >> m;
	
	int from,to;
	
	for(int i = 0; i < m; i++){
		
		cin >> from >> to;
		cout << timeTable[from][to] << "\n";
		
	}
	
}

int main() {
	cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
	init();
	setting();
	floyd();
	solve();
	
	return 0;
}