[c++][백준 21940][플로이드-와샬] 가운데에서 만나기 - 컴도리돌이

---

21940번: 가운데에서 만나기

---

해당 문제는 플로이드 와샬로 해결하였다. 일단 플로이드-와샬이 뭔지 알아야 한다. 플로이드-와샬이란 모든 최단 경로를 구하는 방법이다. 

 

플로이드-와샬로 문제 푸는 과정

 

문제를 해결하기 위한 setting

1. 크기가 n+1이 정방 2차원 배열을 사용하였고, 해당 2차원 배열의 모든 값을 생각보다 큰 수를 입력해서 넣었다.  

2. 문제에서 제공하는 경로에 대한 값을 넣어 줬다. 2차원 배열[출발][도착] = 시간

3. 자기 자신으로 가는 것은 없다. 2차원 배열[i][i] = 0

4. 플로이드-와샬  2차원 배열[출발][경유] + 2차원 배열[경유][도착] < 2차원 배열[출발][도착] 일 경우 해당 값 업데이트.

 

문제 해결 과정

1. 주어진 위치만큼 반복문을 실행하고 친구들 수만큼 반복문을 실행한다.

2. 주어진 위치에서 친구들 위치의 경로가 존재하지 않는다면(값이 생각보다 큰 수) 해당 break 시키고 다음 위치 실행.

3. 경로가 모두 존재한다면 해당 왕복 값 중에서 가장 큰 값 중에서 최소가 되는 도시를 answer 함수에 넣어준다. 이다음은 문제에 시키는 데로 하면 된다.~~

---

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int n,m,k;

vector<vector<int>> dp,matrix;
vector<int> friend_,answer;
void input(){
    ios_base::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);

    cin >> n >> m;
    dp.resize(n+1,vector<int>(n+1,200000));
    for(int i=0,a,b,t; i<m ;i++){
        cin >> a >> b >> t;
        dp[a][b] = t;
    }

    for(int i=1; i<= n ;i++){
        dp[i][i] = 0;
    }

    cin >> k;
    friend_.resize(k);
    for(int i=0; i<k; i++) cin >> friend_[i];
}

void Floyed_Warshall(){
    for(int k=1; k<=n ;k++){
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n;j++){
                if(dp[i][k] + dp[k][j] < dp[i][j]){
                    dp[i][j] = dp[i][k] + dp[k][j];
                }
            }
        }
    }
}

void result(){
    int tt =5000000;
    for(int i=1; i<= n; i++){
        int sum=0;
        bool flag = true;
        for(int j=0 ; j<k; j++){
            if(dp[friend_[j]][i] == 200000 or dp[i][friend_[j]] == 200000){
                flag = false;
                break;
            }
            sum = max(sum,dp[friend_[j]][i] + dp[i][friend_[j]]);
        }
        if(flag){
            if(sum <= tt){
                if(sum < tt){
                    answer.clear();
                    answer.push_back(i);
                    tt = sum;
                }
                else if(sum == tt){
                    answer.push_back(i);
                }
            }
        }
    }
    for(auto a : answer) cout << a << ' ';
}

void solution(){
    input();
    Floyed_Warshall();
    result();
}

int main(){
    solution();
    return 0;
}

---