백준 : 21940번 가운데에서 만나기 (c++)

백준 링크

https://www.acmicpc.net/problem/21940

21940번: 가운데에서 만나기

 

•  

예제 입력 1 복사

4 9
1 2 9
2 3 9
3 1 9
1 4 1
4 1 1
2 4 1
4 2 1
3 4 1
4 3 1
3
1 2 3

예제 출력 1 복사

4

예제 입력 2 복사

3 3
1 2 1
2 3 1
3 1 1
2
1 2

예제 출력 2 복사

1 2 3

코드 풀이

크게 3단계로 구분

• 입력값 할당
• 플로이드 와샬 실행
• 결과 출력

 

코드

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

using namespace std;

#define INF 1000000000

int Graph[201][201];

int N, M;
int K;
vector<int> FriendsCity;

void Input()
{
    cin >> N >> M;

    fill(Graph[0], Graph[N] + N, INF);

    for (int i = 1; i <= N; ++i)
    {
        Graph[i][i] = 0;
    }

    int CityA, CityB, Time;
    for (int i = 0; i < M; ++i)
    {
        cin >> CityA >> CityB >> Time;

        Graph[CityA][CityB] = Time;
    }

    cin >> K;

    FriendsCity.resize(K);

    for (int i = 0; i < K; ++i)
    {
        cin >> FriendsCity[i];
    }
}

void Floyed_Warshall()
{
    for (int i = 1; i <= N; ++i)
    {
        for (int j = 1; j <= N; ++j)
        {
            for (int k = 1; k <= N; ++k)
            {
                Graph[j][k] = min(Graph[j][k], Graph[j][i] + Graph[i][k]);
            }
        }
    }
}

void Result()
{
    pair<int, int> MinPair = { INF, 0 };
    vector<pair<int, int>> vecPair;

    for (int i = 1; i <= N; ++i)
    {
        int RoundTripMax = 0;
        for (int j = 0; j < FriendsCity.size(); ++j)
        {
            if (Graph[FriendsCity[j]][i] == INF || Graph[i][FriendsCity[j]] == INF)
                break;

            RoundTripMax = max(RoundTripMax, Graph[FriendsCity[j]][i] + Graph[i][FriendsCity[j]]);
        }

        if (MinPair.first >= RoundTripMax)
        {
            MinPair = { RoundTripMax, i };
            vecPair.push_back(MinPair);
        }
    }
    sort(vecPair.begin(), vecPair.end());

    int MinNumb = vecPair[0].first;
    for (auto pair : vecPair)
    {
        if (MinNumb == pair.first)
        {
            cout << pair.second << ' ';
        }
    }
}

int main() 
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    Input();

    Floyed_Warshall();

    Result();
    
    return 0;
}