🔗 문제
1956번: 운동
첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의
www.acmicpc.net
✍️ 풀이
방향 그래프로 표현되는 경로에, 두 정점의 최단 거리를 구한다?
플루이드 와샬을 이용해서 푼다.
- 그래프가 주어졌을 때 두 정점의 최단 거리를 구할 때 사용한다.
- 그래프를 인접 행렬로 표현하며, 아직 경로를 찾지 못한 곳은 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;
}