[11404] 플로이드 - 최단 경로 ★☆☆ / 복습 ○

[ 문제 ] : https://www.acmicpc.net/problem/11404

11404번: 플로이드

---

[ 문제 접근 ]

 

기본적인 플로이드 와샬 문제이다. 

 

1. 초기화

 - d[i,j] 를 초기화 해준다. ( i 랑 j 가 같으면 0 으로 아니라면 INF 로)

 

2. 그래프 입력을 받으면서 서로 연결된 노드가 있다면 거리를 업데이트 해준다.

 

3. 플로이드 와샬 알고리즘을 사용한다.

 

---

[ 최종 코드 ]

#include<iostream>
#include<vector>
#include<algorithm>


using std::cout; using std::cin;
using std::vector; 

int n, m;
const int INF = 987654321;
vector<std::pair<int, int>> graph[101];
int dist[101][101];


void floyd() {
	for (int k = 1; k <= n; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
            	if(i == j ) continue; // 자신을 연결하는 경우는 없다고 문제에서 주어짐.
				dist[i][j] = std::min(dist[i][j], dist[i][k] + dist[k][j]);
			}
		}
	}

}

int main() {
	std::ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);
	
	cin >> n >> m;

	// 초기화.
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (i == j)dist[i][j] = 0;
			else { dist[i][j] = INF; }
		}
	}

	while (m--) {
		int a, b, c;
		cin >> a >> b >> c;
		graph[a].push_back({ b,c });
		dist[a][b] = std::min(dist[a][b], c);  // 문제를 잘 읽어봐야한다.
	}
	floyd();

	// 정답 출력.
	
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			dist[i][j] == INF ? cout << 0 << " " : cout << dist[i][j] << " ";
		}
		cout << '\n';
	}

	
	return 0;
}

---

[ Key Point ]

 

👉 문제에서 시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다고 하였으니 

     같은 간선이 여러 번 주어질 수 있으며, 그땐 가장 비용이 낮은 간선을 저장해야 한다.

     => 이거 생각 못해서 여러번 틀렸다.

line 45 ) dist[a][b] = std::min(dist[a][b], c);

 

 

---

[ 다른 사람 풀이 ]

 

ref :: https://intaehwang.tistory.com/89

ref :: https://ongveloper.tistory.com/329