백준 17270 연예인은 힘들어

문제 링크 : 백준 17270 연예인은 힘들어

플로이드-워셜 문제! 중간 지점 찾아주는 과정을 추가해주면 된다.
입력 - 플로이드-워셜을 마치고 나면은,
각 space마다 for문을 돌려야 하는데, 이 때,
1) 최단 거리 합을 가지는 중간 지점들(candidate)을 찾고
2) 최단 거리 합을 가지는 중간 지점에서 지헌이가 이동하는 거리가 성하의 이동거리보다 짧은지 확인하며
3) 지헌이 입장에서 1,2번 조건을 만족하는지 최적의 cost를 갖는 중간 지점을 찾는다.
이 때, 최적의 cost가 변하지 않았다면 (즉, best_Cost = INF라면) -1을 출력하고, 그렇지 않다면 중간 지점을 출력한다.

#include <algorithm>
#include <iostream>
#include <vector>
#define INF 987654321
using namespace std;
int V, M;
int J, S;
int ret = -1;
int dp[101][101];
int cost;
int best_Cost;

void input() {
  cin >> V >> M;
  for (int i = 1; i <= V; i++) {
    for (int j = 1; j <= V; j++) {
      dp[i][j] = INF;
      if (i == j) {
        dp[i][j] = 0;
      }
    }
  }
  best_Cost = INF;
  cost = INF;
  
  for (int i = 0; i < M; i++) {
    int a, b, c;
    cin >> a >> b >> c;
    dp[a][b] = min(c, dp[a][b]);
    dp[b][a] = min(c, dp[b][a]);
  }
  cin >> J >> S;
}

void floyd_Warshall() {
  for (int k = 1; k <= V; k++) {
    for (int i = 1; i <= V; i++) {
      for (int j = 1; j <= V; j++) {
        if (dp[i][j] > dp[i][k] + dp[k][j]) {
          dp[i][j] = dp[i][k] + dp[k][j];
        }
      }
    }
  }
}

void candidate() {
  for (int i = 1; i <= V; i++) {
    if (i == J || i == S) {
      //지헌이나 성하의 위치와 동일할 경우 pass
      continue;
    }
    //최단 거리 합 구해놓기
    cost = min(cost, dp[J][i] + dp[S][i]);
  }

  for (int i = 1; i <= V; i++) {
    if (i == J || i == S)
      continue;
    if (cost == dp[J][i] + dp[S][i]) { // && dp[J][i] <= dp[S][i]){
      //최단거리 이고,
      //지헌이가 더 짧게 움직이는가?
      if (dp[J][i] <= dp[S][i]) {
        best_Cost = min(best_Cost, dp[J][i]);
      }
    }
  }
  if (best_Cost == INF)
    return;
  for (int i = 1; i <= V; i++) {
    if (i == J || i == S)
      continue;
    if (best_Cost != INF && cost == dp[J][i] + dp[S][i] &&
        best_Cost == dp[J][i]) {
      ret = i;
    }
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  input();
  floyd_Warshall();

  candidate();
  cout << ret;
  return 0;
}