11404번: 플로이드
첫째 줄에 도시의 개수 n(1 ≤ n ≤ 100)이 주어지고 둘째 줄에는 버스의 개수 m(1 ≤ m ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그
www.acmicpc.net
1. 풀이방법
- 문제를 읽다보면 문제에서는 버스, 즉 간선(단방향)이 비용(가중치)를 각각 가지고 있다.
- (->BFS로는 구할 수 없겠구나 ! 라는 생각)
- 다익스트라 또는 플로이드 워셜 (대표적)
- 근데 출력을 보니 모든 도시에서 자신을 제외한 모든 점까지의 최단거리를 출력하는 문제 (자신 또는 못가는 경우 0 )
- (-> 플로이드 워셜 ! )
2. 주의사항
- 구현 시 도시사이의 거리를 입력 받기전 가장 큰 값으로 초기화 해줘야 하는데 COST가 100,000을 넘지 않는 다는 말을
- 보고 100001으로 정의해두었다가(INF) 계쏙 98퍼에서 오류가 뜨길래...생각해보니...
- 거쳐서 가는경우 100,000을 그냥 넘을 수 있다는 것......!!! 주의주의.... 그래서 그냥 987654321로 초기화 하였다
3. 나의코드
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
#define INF 987654321
int n, m;
int CityToCity[101][101];
void inputs() { //입력함수
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) { //초기화
if (i == j) continue;
CityToCity[i][j]=INF;
}
}
int start, end, cost;
for (int i = 0; i < m; i++) {
cin >> start >> end >> cost;
if (CityToCity[start][end] > cost) {
CityToCity[start][end] = cost;
}
}
}
void Searchmin() {
for (int a = 1; a <= n; a++) {
for (int b = 1; b <= n; b++) {
for (int c = 1; c <= n; c++) {
if (CityToCity[b][a] != INF && CityToCity[a][c] != INF) { //거쳐서 갈 수 있는 경우
CityToCity[b][c] = min(CityToCity[b][c], (CityToCity[b][a] + CityToCity[a][c]));
}
}
}
}
}
void outputs() { //출력함수
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (CityToCity[i][j] == INF||i==j) cout << 0 << " ";
else cout << CityToCity[i][j] << " ";
}
cout << "\n";
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
inputs();
Searchmin();
outputs();
return 0;
}'알고리즘 문제풀이 > DFS와 BFS' 카테고리의 다른 글
| 백준 15684 [C++] (0) | 2020.12.09 |
|---|---|
| 백준 15683 [C++] (0) | 2020.12.08 |
| 백준 16234[C++] (0) | 2020.10.25 |
| 백준 18405 [C++] (0) | 2020.10.25 |
| 백준 17471 [C++] (0) | 2020.10.19 |
