[이것이 코딩 테스트다] 미래 도시

❓ 문제 ❓
출발지에서 방문지, 도착지까지의 최단거리를 구하시오

💯 문제 풀이 💯
각 도시별로 최단거리를 구한후 출발지부터 방문지, 방문지부터 도착지까지의 거리를 합하면 된다.
플로이드 와샬 알고리즘!

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int INF = 1000000;
int map[101][101];
int n, m, arrive, visit;	//회사 개수, 경로 개수, 도착지, 방문지
int main() {
	cin >> n >> m;

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (i == j) continue;
			map[i][j] = INF;
		}
	}

	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		map[a][b] = map[b][a] = 1;
	}
	cin >> arrive >> visit;

	//플로이드 와샬
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			for (int k = 1; k <= n; k++) {
				map[j][k] = min(map[j][k], map[j][i] + map[i][k]);
			}
		}
	}
	if (map[1][visit] + map[visit][arrive] >= INF) cout << -1;
	else cout << map[1][visit] + map[visit][arrive];

}