BOJ 21940 가운데에서 만나기

📝 문제 정보

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

🧐 관찰 및 접근

일단 가중치가 있는 방향 그래프인데..
어떤 도시 $X$에 대해 준형이와 친구들이 살고있는 모든 도시에 대해 왕복 시간을 구할 수 있을까?
- $N$이 충분히 작으므로, 플로이드 워셜을 사용해서 모든 도시간의 이동시간을 구할 수 있겠다.
- 이후에는 모든 도시 $X$에 대해 $K$번의 계산으로 왕복시간들의 최댓값을 구할 수 있다.
시간복잡도 $O(N^3 + NK)$로 풀릴 것 같다!

💻 풀이

코드 (C++):

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

    rep(i, 0, N) rep(j, 0, N) cost[i][j] = 1e15;
    rep(i, 0, N) cost[i][i] = 0;
    rep(i, 0, M){
        int u, v, w; cin >> u >> v >> w;
        u--; v--;
        cost[u][v] = w;
    }
    rep(k, 0, N) rep(i, 0, N) rep(j, 0, N) cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j]);

    cin >> K;
    vector<int> v(K), ans;
    rep(i, 0, K) cin >> v[i];

    ll mn = 1e15;
    rep(X, 0, N){
        ll tmp = 0;
        for(auto c: v) tmp = max(tmp, cost[X][c-1] + cost[c-1][X]);
        if(tmp < mn){
            mn = tmp;
            ans.clear();
        }
        if(tmp == mn) ans.push_back(X+1);
    }
    for(auto c: ans) cout << c << ' ';
}