[ 백준 1238 ] 파티 (C++)

[문제보기]

 

[해결과정]

 1. 2차원 배열 초기값을 -1로 셋팅

 2. input : v[a][b] = c ---> a에서 b까지 가는데 c시간이 걸린다.

 3. 2차원 배열을 순회하며 -1인 값을 987987987(최대 값)으로 변경 

 4. 플로이드 와샬 알고리즘 실행

 5. 모든 노드에 대한 탐색을 실행

  -> i에서 x까지의 거리, x에서 i까지의 거리를 합하고 ans와 비교하여 큰 값 갱신

 

[소스코드]

#include<iostream>
#include<vector>
#include<set>
#include<string>
#include<queue>
#include<algorithm>
#include<math.h>
#include<memory.h>
typedef long long ll;
using namespace std;
const int INF = 2e9;
const int MAX = 1005;
 
int n,m,x;
int v[MAX][MAX];
int arr[MAX][MAX];
 
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
 
    cin >> n >> m >> x;
    int a, b, c;
    memset(v, -1, sizeof(v));
    for (int i = 0; i < m; i++) {
        cin >> a >> b >> c;
        v[a][b] = c;
    }
 
    for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++)
        if (v[i][j] == -1) v[i][j] = 987987987;
    
    // 거쳐야하는 점
    for (int k = 1; k <= n; k++) {
        // 출발 점
        for (int i = 1; i <= n; i++) {
            // 도착 점
            for (int j = 1; j <= n; j++) {
                if (v[i][k] + v[k][j] < v[i][j]) v[i][j] = v[i][k] + v[k][j];
             }
        }
    }
 
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        if (i == x) continue;
        int temp = 0;
 
        // i -> x 까지 거리
        temp += v[i][x];
        // x -> i 까지 거리
        temp += v[x][i];
 
        if (temp > ans) ans = temp;
    }
 
    cout << ans << "\n";
 
    return 0;
}

 

[해결 과정 중 실수한 부분]

 플로이드 와샬을 조금 활용한 문제이다.. 그래프중에서는 플로이드 와샬이 가장 쉬운 것 같다.!

 

[관련 문제 혹은 비슷한 문제]

 플로이드 와샬