[C++] 백준 1956번: 운동

🔗 문제

1956번: 운동

1956번: 운동

 

✍️ 풀이

 

방향 그래프로 표현되는 경로에, 두 정점의 최단 거리를 구한다?

 

플루이드 와샬을 이용해서 푼다.

• 그래프가 주어졌을 때 두 정점의 최단 거리를 구할 때 사용한다.
• 그래프를 인접 행렬로 표현하며, 아직 경로를 찾지 못한 곳은 INF이다. 

 

플루이드 와샬의 핵심은 a→b로 이동하고자 할때 중간 노드를 고려한다는 점이다. 

O(V^3)의 시간이 걸리지만 v가 400으로 작은 축에 속해서 문제를 풀 수 있다.  

 

💾  소스

#include <iostream>
#include <vector>
#include <cmath>

const int INF = 1e9;

std::vector<std::vector<int>> adj;
int V, E, answer = INF;

void input()
{
	int a, b, cost;

	std::cin >> V >> E;

	adj.resize(V + 1, std::vector<int>(V + 1, INF));
	
	while (E--)
	{
		std::cin >> a >> b >> cost;
		adj[a][b] = cost;
	}
}

int main()
{
	input();

  //플루이드 워셜
	for (int k = 1; k <= V; ++k)
		for (int i = 1; i <= V; ++i)
			for (int j = 1; j <= V; ++j)
				adj[i][j] = std::min(adj[i][j], adj[i][k] + adj[k][j]);

	for (int i = 1; i <= V; ++i) // 원점으로 돌아오니까 여기서 정답 찾아야함
		answer = (answer < adj[i][i] ? answer : adj[i][i]);

	std::cout << (answer == INF ? -1 : answer);
    
    return 0;
}