[BAEKJOON] 1956번 : 운 동

문 제

 

소 스  코 드

#include <iostream>
#include <vector>
#include <algorithm>
// 플로이드 워셜

constexpr int INF	{ 100'000'000 };

struct Edge {
	int mNext;
	int mCost;
};

int dist[401][401];


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

	int V, E;
	std::cin >> V >> E;
	for (int i = 0; i <= V; ++i) {
		std::fill_n(dist[i], V + 1, INF);
		dist[i][i] = 0;
	}

	int a, b, c;
	for (int i = 0; i < E; ++i) {
		std::cin >> a >> b >> c;
		dist[a][b] = std::min(dist[a][b], c);
	}

	for (int m = 1; m <= V; ++m) {
		for (int x = 1; x <= V; ++x) {
			for (int y = 1; y <= V; ++y) {
				dist[x][y] = std::min(dist[x][y], dist[x][m] + dist[m][y]);
			}
		}
	}

	int total = INF;
	for (int i = 1; i <= V; i++) {
		for (int j = i + 1; j <= V; j++) {
			if (INF != dist[i][j] && INF != dist[j][i])
				total = std::min(total, dist[i][j] + dist[j][i]);
		}
	}

	if (INF == total)	std::cout <<"-1 \n";
	else				std::cout << total << '\n';

	return 0;
}

 

풀 이

 

• 플로이드-워셜 알고리즘

플로이드-워셜 알고리즘을 통하여,

각 지점에서 지점까지의 거리를 알 수 있기 때문에,

 

각 점에서 점 까지의 왕복 거리를 검사하여 답을 구할 수 있다.

 

출 력 값

 

 

문 제  출 처

문제 링크 : www.acmicpc.net/problem/1956

1956번: 운동