1507 궁금한 민호

1507 궁금한 민호 https://www.acmicpc.net/problem/1507

최단 이동 시간이 구해져있는 표가 주어진다.
이 표를 이용해서 도로 개수가 최소일 때 모든 도로의 이동 시간을 구하는 문제다.

어렵진 않은 문제인데 헷갈렸다.
11097 도시 계획 https://www.acmicpc.net/problem/11097
풀이 https://lyzqm.blogspot.kr/2017/07/11097.html
이 문제에서도 불필요한 간선을 제거하는데 플로이드 와샬 알고리즘을 사용한다.

$dist[n][m] == dist[n][k] + dist[k][m]$이면 $n,m$간선을 삭제시킬 수 있는것이다.
즉, 이렇게 도로 개수를 줄일 수 있다.

#include <cstdio> int N; int in[21][21]; bool v[21][21]; int main() {     scanf("%d", &N);     for (int n = 0;n < N;n++) for (int m = 0;m < N;m++) scanf("%d", &in[n][m]);     for (int k = 0;k < N;k++) for (int n = 0;n < N;n++) for (int m = 0;m < N;m++) {         if (n == m || n == k || k == m) continue;         if (in[n][m] == in[n][k] + in[k][m]) v[n][m] = true;         else if (in[n][m] > in[n][k] + in[k][m]) { printf("-1\n"); return 0; }     }     int ans = 0;     for (int n = 0;n < N;n++) for (int m = n;m < N;m++) {         if (!v[n][m]) ans += in[n][m];     }     printf("%d\n", ans);     return 0; } Colored by Color Scripter

cs