[백준]비밀 모임(13424)

문제 링크 : [백준]비밀 모임(13424)

문제 설명

N개의 방이 주어지고, M개의 양방향 간선이 주어집니다.
이때, 정해진 K개의 방에서 출발하여 특정 방에서 모이려고 할 때, 모이기 위해 이동하는 거리의 합이 최소가 되는 방 번호를 구하세요.

입력

T(테스트 케이스 수)
N(방의 갯수, 1 <= N <= 100)
M(간선의 수, 1 <= M <= N * (N - 1) / 2)
Si Ei Ci(출발, 도착, 비용, 1 <= Ci <= 1,000)
K(출발할 방의 갯수, 1 <= N)
Di(출발 할 방의 번호)

2
6 7
1 2 4
1 3 1
1 5 2
2 3 2
3 4 3
4 5 2
6 5 1
2
3 5
4 5
1 2 2
1 3 1
2 3 2
2 4 3
3 4 6
2
3 4

출력

1
2

카테고리

#플로이드와샬

시간 복잡도 상한

O(N3)

해결 방법

1. 답을 구하기 위해서는 출발할 모든 방에서 출발하여 모든 방에 도착하는 경우를 알아야 그 중 최소값을 구할 수 있습니다.
2. 플로이드와샬을 통해 N3에 모든 방 사이에 최소비용을 구할 수 있습니다.
3. 주어진 모든 출발지에서 모든 방에 도착하는 비용들의 합을 구하면서 최소값을 구하면 됩니다.

시간복잡도

O(N3)

코드

#include<cstdio>
#include<string.h>
#include<algorithm>
using namespace std;
int t,n,m,l,k,d[101][101],i,j,e[100],s,p;
int main(){
    scanf("%d",&t);
    while(t--){
        for(i=1;i<101;i++)for(j=1;j<101;j++)d[i][j]=i!=j?999999:0;
        s=999999;
        scanf("%d%d",&n,&m);
        while(m--){
            scanf("%d%d%d",&i,&j,&k);
            d[i][j]=d[j][i]=k;
        }
        scanf("%d",&l);
        for(i=0;i<l;i++)scanf("%d",e+i);
        for(k=1;k<=n;k++)for(i=1;i<=n;i++)for(j=1;j<=n;j++)d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
        for(i=1;i<=n;i++){
            for(k=j=0;j<l;j++)k+=d[e[j]][i];
            if(s>k)s=k,p=i;
        }
        printf("%d\n",p);
    }
}