링크
https://www.acmicpc.net/problem/1507
문제
강호는 N개의 도시로 이루어진 나라에 살고 있다. 각 도시는 M개의 도로로 연결되어 있으며, 각 도로를 지날 때 필요한 시간이 존재한다. 도로는 잘 연결되어 있기 때문에, 도시 A에서 B로 이동할 수 없는 경우는 존재하지 않는다.
도시 A에서 도시 B로 바로 갈 수 있는 도로가 있거나, 다른 도시를 거쳐서 갈 수 있을 때, 도시 A에서 B를 갈 수 있다고 한다.
강호는 모든 쌍의 도시에 대해서 최소 이동 시간을 구해놓았다. 민호는 이 표를 보고 원래 도로가 몇 개 있는지를 구해보려고 한다.
예를 들어, 예제의 경우에 모든 도시 사이에 강호가 구한 값을 가지는 도로가 존재한다고 해도 된다. 하지만, 이 도로의 개수는 최솟값이 아니다. 예를 들어, 도시 1-2, 2-3, 1-4, 3-4, 4-5, 3-5를 연결하는 도로만 있다고 가정해도, 강호가 구한 모든 쌍의 최솟값을 구할 수 있다. 이 경우 도로의 개수는 6개이고, 모든 도로의 시간의 합은 55이다.
모든 쌍의 도시 사이의 최소 이동 시간이 주어졌을 때, 이 나라에 존재할 수 있는 도로의 개수의 최솟값일 때, 모든 도로의 시간의 합을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 도시의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에 각각의 도시 사이에 이동하는데 필요한 시간 (≤ 10,000)이 주어진다. A에서 B로 가는 시간과 B에서 A로 가는 시간은 같다. 또, A와 B가 같은 경우에는 필요한 시간은 0이다.
출력
첫째 줄에 도로 개수가 최소일 때, 모든 도로의 시간의 합을 출력한다. 불가능한 경우에는 -1을 출력한다.
예제 입력 및 출력
풀이법
일반적인 최단거리를 구하는 플로이드-와샬 알고리즘 문제들과는 약간 다른 접근법이 필요했던 문제.
플로이드를 역으로 추적하는 방법이 필요하다
i->j로 이동시에 입력으로 들어온 경로가 k를 거쳐서 가야하는 최소 경로라면 해당 dist배열의 위치를 false로 바꿔줌으로써 direct경로가 아님을 표시한다.
풀이 코드(C++)
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<deque>
#include<stack>
#include<string>
#include<list>
#include<map>
#include<set>
#include<unordered_map>
#include<unordered_set>
#include<bitset>
#include<tuple>
#include<functional>
#include<utility>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<complex>
#include<cassert>
#define X first
#define Y second
#define pb push_back
#define MAX 21
#define INF 1e9
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using dbl = double;
using ldb = long double;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using vi = vector<int>;
bool dist[MAX][MAX];
int input[MAX][MAX];
bool impossbile;
int n;
void reverse_floyd(int n){
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 || k == i) continue; // 서로 다른 두 도시의 경우에만
if(input[i][j] > input[i][k] + input[k][j]){
//플로이드 알고리즘의 결과가 아님
//i-j시간이 최소가 아님, k 거쳐가면 시간이 단축되는 경우 존재
impossbile = true;
return;
}
else if(input[i][j] == input[i][k] + input[k][j]){
dist[i][j] = false; //direct 경로가 아니면 i-j연결도로 삭제
}
}
}
}
}
int main(){
fastio;
cin >> n;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
dist[i][j] = true; // 모든 도시가 연결되어 있다.
}
}
for(int i = 1; i<= n; i++){
for(int j = 1; j <= n; j++){
cin >> input[i][j];
}
}
reverse_floyd(n);
int ans = 0; // 모든 도로의 합
for(int i = 1; i<= n; i++){
for(int j = 1; j <= n; j++){
if(dist[i][j] == true){
ans += input[i][j]; // direct 경로가 있으면 true
}
}
}
ans /= 2; // 계산 결과가 중복되어 있으므로 2로 나누어줌
if(impossbile) cout << -1;
else cout << ans;
return 0;
}참고
