쌓고 쌓다

[백준] 운동 1956번 C++ 풀이 본문

알고리즘/백준

[백준] 운동 1956번 C++ 풀이

승민아 2021. 12. 24. 16:24

 

https://www.acmicpc.net/problem/1956

 

1956번: 운동

첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의

www.acmicpc.net

#include <iostream>
#include <vector>
using namespace std;
int V, E;
int arr[401][401];
int res = 987654321;
int main(void)
{
	int a, b, c;
	cin >> V >> E;
	for (int i = 0; i < E; i++)
	{
		cin >> a >> b >> c;
		arr[a][b] = c;
	}
	
	for(int i=1;i<=V;i++)
		for (int j = 1; j <= V; j++)
		{
			if (arr[i][j] == 0)
				arr[i][j] = 987654321;
		}

	for (int k = 1; k <= V; k++)
		for (int i = 1; i <= V; i++)
			for (int j = 1; j <= V; j++)
				if (arr[i][j] > arr[i][k] + arr[k][j])
				{
					arr[i][j] = arr[i][k] + arr[k][j];
					if (i == j) // 자기에게 돌아오는 길
						res = min(res, arr[i][j]);
				}

	if (res == 987654321) // 987654321이면 길이 없음
		cout << "-1";
	else
		cout << res;
}

플로이드 와샬 알고리즘을 사용하면 된다~

저작자표시

'알고리즘 > 백준' 카테고리의 다른 글

[백준] 문자열 집합 14425번 C++ 풀이  (0) 2021.12.26
[백준] 풍선 터뜨리기 2346번 C++ 풀이  (0) 2021.12.25
[백준] 카드 구매하기2 16194번 C++ 풀이  (0) 2021.12.23
[백준] 1로 만들기2 12852번 C++ 풀이  (0) 2021.12.22
[백준] 그림 1926번 C++ 풀이  (0) 2021.12.21
'알고리즘/백준' Related Articles more
Comments