글 읽기 - k,i,j 세 정점이 모두 달라야 하는 이유가 뭔가요?

(追記) (追記ここまで)

k,i,j 세 정점이 모두 달라야 하는 이유가 뭔가요?

1507번 - 궁금한 민호

shinbian11 4년 전 0

47,50,51번째 줄에서 k,i,j는 모두 다른 정점이라는 조건을 붙이지 않아서 틀렷더라고요. 그래서 그 조건을 한번 붙여봤더니 정답처리가 되었는데. 왜 i,j,k는 다 다른 점이어야만 하나요? 플로이드에 원래 기본적으로 있는 조건은 아닌것 같아서요..

#include <bits/stdc++.h>
// F_I 사용하면 cin 과 scanf 를 섞어서 쓰면 안된다!
#define F_I ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pl;
typedef pair<int, int> pi;
ll Min(ll a, ll b) { return (a < b) ? a : b; }
ll Max(ll a, ll b) { return (a < b) ? b : a; }
ll gcd(ll m, ll n) { if (n == 0) return m; return gcd(n, m % n); } //최대공약수
ll lcm(ll m, ll n) { return m * n / gcd(m, n); } //최소공배수
int arr[21][21];
int unused[21][21];
int main()
{
 F_I;
 
 //[백준] 1507번 : 궁금한 민호 (플로이드)
 /*
 - 모든 도시 사이의 최소 이동 시간이 주어졌다는 것은, 입력으로 이미 최단 시간이 주어졋다는 의미이다.
 - i j
 k
 만약 i--->j로 가는 cost와 i-->k + k-->j의 cost의 합이 같다면, i--->j의 경로는 쓸모가 없어지는 것이다.
 모든 k에 대해 탐색하면서, 이렇게 쓸모없는 경로들을 제거하는 방식으로 가야한다.
 */
 int n;
 cin >> n;
 for (int i = 1; i <= n; i++)
 {
 for (int j = 1; j <= n; j++)
 cin >> arr[i][j];
 }
 for (int k = 1; k <= n; k++)
 {
 for (int i = 1; i <= n; i++)
 {
 if (k == i) continue; //k와 i는 같으면 안됨, 왜?
 for (int j = 1; j <= n; j++)
 {
 if (k == j) continue; //k와 j는 같으면 안됨, 왜?
 if (i == j) continue; //i와 j는 같으면 안됨, 왜?
 if (arr[i][j] > arr[i][k] + arr[k][j])
 {
 cout << -1 << '\n';
 return 0;
 }
 if (arr[i][j] == arr[i][k] + arr[k][j]) //값이 같으면, i-->j의 경로는 쓸모없는 경로가 된다.
 unused[i][j] = true;
 }
 }
 }
 int ans = 0;
 for (int i = 1; i <= n; i++)
 {
 for (int j = 1; j <= n; j++)
 {
 if (unused[i][j] == false) //쓸모있는 경로의 cost만 값에 더한다.
 ans += arr[i][j];
 }
 }
 cout << ans / 2 << '\n'; // i-->j 와 j-->i의 값을 둘 다 더했으니, 하나는 빼주어야 한다.
 return 0;
}

devbelly 4년 전 1

59번째줄은 서로다른 두 다리(i-k,k-j)를 사용한거나 하나의 다리(i-j)를 사용한 효과가 같으면 다리 하나를 없애는 코드인데

47번째줄에서 k==j와 같은 검사를 해주지 않았다면

59번째줄은 arr[i][j]==0+arr[i][j]와 같은 if문도 true로 처리하여 그냥 다리가 있다면 없애버리는것 같아요

shinbian11 4년 전 0

감사합니다!! 이해가 되었어요!

댓글을 작성하려면 로그인해야 합니다.

(追記) (追記ここまで)

Baekjoon Online Judge

채점 현황

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

사업자 등록 번호: 541-88-00682
대표자명: 최백준
주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
전화번호: 02-521-0487 (이메일로 연락 주세요)
이메일: contacts@startlink.io
통신판매신고번호: 제 2017-서울서초-2193 호

한국어 | English (Beta)

문제

문제

출처

ICPC

k,i,j 세 정점이 모두 달라야 하는 이유가 뭔가요?

shinbian11 4년 전 0

devbelly 4년 전 1

shinbian11 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말