어흥
[백준 11780] 플로이드 2 (C++) 본문
728x90
반응형
문제 링크: https://www.acmicpc.net/problem/11780
1. 주의할 점
- 플로이드 와샬 알고리즘을 진행하면서 경로를 저장해야 빠르게 문제를 풀 수 있다
- 플로이드 와샬 알고리즘을 진행하면서 새로운 최단 경로가 생성되는 경우, I~K까지의 경로 + K~J까지의 경로를 I~J까지의 경로에 갱신해서 저장한다. 단, K가 2번 입력되지 않도록 설정한다
- 간선의 정보를 입력받을 때, I~J까지의 경로가 1가지가 아닐 수 있다
2. 구현
- Arr[][] 배열을 전부 MAX로 초기화한다. 단, I==J인 경우 0으로 초기화한다
- Arr[][] 배열을 통해 각 노드까지의 거리를 입력 받으며, 기존의 값보다 작은 경우에만 수정한다
- 플로이드 와샬을 수행하며 최단경로가 갱신될때 최단경로의 값, 최단경로에 이르기까지의 경로를 갱신한다
- Arr[][] 배열을 먼저 출력한 후, V[][] 벡터를 통해 경로를 출력한다
#define MAX 9876543210
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
long long arr[101][101];
vector<int> v[101][101];
int node, edge, s, e, val;
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
cin >> node >> edge;
for(int i=1;i<=node;i++)
for (int j = 1; j <= node; j++) {
if (i == j) arr[i][j] = 0;
else arr[i][j] = MAX;
v[i][j].push_back(i);
v[i][j].push_back(j);
}
for (int i = 0; i < edge; i++) {
cin >> s >> e >> val;
if(arr[s][e]>val)
arr[s][e] = val;
}
for (int k = 1; k <= node; k++) {
for (int i = 1; i <= node; i++) {
for (int j = 1; j <= node; j++) {
if (arr[i][j] > arr[i][k] + arr[k][j]) {
arr[i][j] = arr[i][k] + arr[k][j];
vector<int> t = v[k][j];
v[i][j].clear();
v[i][j] = v[i][k];
for (int m = 1; m < t.size(); m++)
v[i][j].push_back(t[m]);
}
}
}
}
for (int i = 1; i <= node; i++) {
for (int j = 1; j <= node; j++) {
if (arr[i][j] == MAX) arr[i][j]=0;
cout << arr[i][j] << " ";
}
cout << '\n';
}
for (int i = 1; i <= node; i++) {
for (int j = 1; j <= node; j++) {
if (arr[i][j] == 0) cout << 0 << " ";
else {
cout << v[i][j].size() << " ";
for (int k = 0; k < v[i][j].size(); k++)
cout << v[i][j][k] << " ";
}
cout << '\n';
}
}
return 0;
}
728x90
반응형
'알고리즘 > 백준' 카테고리의 다른 글
[백준 14588] Line Friends (Small) (Java) (0) | 2020.07.28 |
---|---|
[백준 6198] 옥상 정원 꾸미기 (C++, Java) (0) | 2020.07.28 |
[백준 18223] 민준이와 마산 그리고 건우 (C++) (0) | 2020.07.27 |
[백준 10836] 여왕벌 (JAVA) (0) | 2020.07.26 |
[백준 17182] 우주 탐사선 (C++) (0) | 2020.07.08 |
Comments