[백준 13424] 비밀 모임 (C++)

문제 링크: www.acmicpc.net/problem/13424

13424번: 비밀 모임

1. 주의할 점

- 다익스트라 혹은 플로이드 와샬 알고리즘에 대해 알고 있어야 한다

 

2. 구현

- 모든 간선에 대한 정보를 TC마다 초기화한다

- 간선에 대한 정보를 Arr[][] 배열에 입력받는다

- floydWarshall() 함수를 통해 각 노드사이의 최단거리를 구한다

- 친구들이 위치한 방을 V벡터에 받은 후, 1~Node번방까지 모두 모임의 방이라고 가정하며 모임방↔친구들이 위치한 방까지의 최단경로의 합을 Temp에 저장한다

- Result가 Temp에 의해 갱신된다면, 갱신을 시킨 방번호 K를 idx에 저장한다

#define MAX 987654321
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int node,edge,s,e,val,test,num;
int arr[101][101];

void floydWarshall(){
    for(int k=1;k<=node;k++)
        for(int i=1;i<=node;i++)
            for(int j=1;j<=node;j++)
                if(arr[i][j]>arr[i][k]+arr[k][j])
                    arr[i][j]=arr[i][k]+arr[k][j];
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin>>test;
    for(int t=0;t<test;t++){
        cin>>node>>edge;
        for(int i=1;i<=node;i++)
            for(int j=1;j<=node;j++){
                if(i==j) arr[i][j]=0;
                else arr[i][j]=MAX;
            }
        for(int i=0;i<edge;i++){
            cin>>s>>e>>val;
            arr[s][e]=val;
            arr[e][s]=val;
        }
        floydWarshall();
        cin>>num;
        vector<int> v;
        int result = MAX,idx;
        for(int i=0;i<num;i++){
            cin>>val;
            v.push_back(val);
        }
        for(int k=1;k<=node;k++){
            int temp=0;
            for(int i=0;i<num;i++)
                temp+=arr[k][v[i]];           
            if(result>temp){
                result=temp;
                idx=k;
            }
        }
        cout<<idx<<'\n';
    }
    return 0;
}