백준 16958번 텔레포트 C++

출처 : https://www.acmicpc.net/problem/16958

먼저 2중 for문으로 한 도시에서 다른 모든 도시까지 가는 거리들을 텔레포트도 고려하여서 구하고,

플로이드-와샬 알고리즘으로 최소 거리를 구했다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>

using namespace std;
typedef long long ll;

struct city {
	city() {};
	city(int s, int x, int y) :s(s), x(x), y(y) {};
	int s;
	int x;
	int y;
};
int n, t, m;
vector<city> v(1001);
vector<vector<int>> dists(1001, vector<int>(1001, 987654321));

int GetDist(int start, int end) {
	int ret;
	if (v[start].s == 1 && v[end].s == 1) {
		ret = min(abs(v[start].x - v[end].x) + abs(v[start].y - v[end].y), t);
	}
	else {
		ret = abs(v[start].x - v[end].x) + abs(v[start].y - v[end].y);
	}
	return ret;
}

void GetMinDist() {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (i == j) continue;
			dists[i][j] = GetDist(i, j);
		}
	}

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			for (int k = 1; k <= n; k++) {
				if (j == k) continue;
				if (dists[j][k] > dists[j][i] + dists[i][k]) {
					dists[j][k] = dists[j][i] + dists[i][k];
				}
			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n >> t;
	for (int i = 1; i <= n; i++) {
		int s, x, y;
		cin >> s >> x >> y;
		v[i] = city(s, x, y);
	}
	GetMinDist();
	cin >> m;
	for (int i = 0; i < m; i++) {
		int start, end;
		cin >> start >> end;
		cout << dists[start][end] << "\n";
	}
};