#include <stdio.h> #include <iostream> #include <vector> #include <map> using namespace std; int cityNum, busNum; int start; int d[110][110]; map<pair<int, int>, int> visited; void floyd() { for(int k = 1; k <= cityNum; k++) { for(int i = 1; i <= cityNum; i++) { for(int j = 1; j <= cityNum; j++) { if(d[i][k] + d[k][j] < d[i][j]) { d[i][j] = d[i][k] + d[k][j]; } } } } } int main(void) { // freopen("B11404_input.txt", "r", stdin); cin >> cityNum >> busNum; for(int i = 1; i <= cityNum; i++) { for(int j = 1; j <= cityNum; j++) { d[i][j] = 199999999; } } for(int i = 1; i <= busNum; i++) { int from, to, weight; cin >> from >> to >> weight; if(visited[{from, to}] == 0) { d[from][to] = weight; visited[{from, to}] = 1; } else { if(weight < d[from][to]) { d[from][to] = weight; } } } floyd(); for(int i = 1; i <= cityNum; i++) { for(int j = 1; j <= cityNum; j++) { // i와 j가 같은 경우는 항상 최소비용 0 if(i == j) { cout << "0 "; } // i에서 j로 갈 수 없는 경우 else if(d[i][j] == 199999999) { cout << "0 "; } else { cout << d[i][j] << " "; } } cout << endl; } return 0; } | cs |
'Baekjoon > Graph' 카테고리의 다른 글
[백준 1507] 궁금한 민호 (Floyd-Warshall) (C/C++) (★★) (0) | 2020.02.08 |
---|---|
[백준 5567] 결혼식 (Floyd-Warshall) (C/C++) (0) | 2020.02.07 |
[백준 2644] 촌수계산 (BFS/Floyd-Warshall) (C/C++) (0) | 2019.12.04 |
[백준 1613] 역사 (Floyd-Warshall) (C/C++) (★) (0) | 2019.11.20 |
[백준 11403] 경로찾기 (Floyd-Warshall) (C/C++) (0) | 2019.11.20 |