#include <stdio.h> #include <iostream> #include <vector> #include <map> using namespace std; int N; int graph[25][25]; int road[25][25]; int roadCnt; int sum; bool flag = false; 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 || j == k || i == k) { continue; } if(graph[i][k] + graph[k][j] == graph[i][j]) { // road[i][j] = 1 구간은 필요없음 road[i][j] = 1; } else if(graph[i][k] + graph[k][j] < graph[i][j]) { flag = true; return; } } } } } int main(void) { // freopen("B1507_input.txt", "r", stdin); cin >> N; for(int i = 1; i <= N; i++) { for(int j = 1; j <= N; j++) { cin >> graph[i][j]; } } floyd(); if(flag) { cout << "-1"; } else { for(int i = 1; i <= N; i++) { for(int j = i; j <= N; j++) { if(i == j) { continue; } if(road[i][j] == 0) { roadCnt++; sum += graph[i][j]; } } } cout << sum; } return 0; } | cs |
'Baekjoon > Graph' 카테고리의 다른 글
[백준 1753] 최단경로 (Dijkstra) (C/C++) (0) | 2020.02.16 |
---|---|
[백준 1991] 트리 순회 (Tree) (C/C++) (0) | 2020.02.16 |
[백준 5567] 결혼식 (Floyd-Warshall) (C/C++) (0) | 2020.02.07 |
[백준 11404] 플로이드 (Floyd-Warshall) (C/C++) (0) | 2020.02.07 |
[백준 2644] 촌수계산 (BFS/Floyd-Warshall) (C/C++) (0) | 2019.12.04 |