BOJ 23807 두 단계 최단 경로 3

📝 문제 정보

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

🧐 관찰 및 접근

무향그래프고, 정해진 정점중 세개 이상의 정점을 지나야 한다..
이걸 경로로 나타내면 $X \rightarrow P_i \rightarrow P_j \rightarrow P_k \rightarrow Z$이 될 것이다.
이때, $X$에서 시작한 경로와 $Z$에서 시작한 최단 경로는 다익스트라로 쉽게 계산할 수 있다.
이제 가운데 $P_j$에서 시작한 최단 경로를 구해서, 각 $P_i, P_k$에 대해 구하면 되겠다.
$O(V+E)$의 다익스트라를 $P \leq 100$번 돌려야 한다. 조금 무거운 4천만정도일거같은데, 6초제한이니 잘 돌것같다.

💻 풀이

코드 (C++):

void solve(){
    ll N, M; cin >> N >> M;
    vector<vector<pll>> links(N+1);
    rep(i, 0, M){
        ll u, v, w; cin >> u >> v >> w;
        links[u].push_back({v, w});
        links[v].push_back({u, w});
    }
    int X, Z; cin >> X >> Z;

    vector<ll> dist_fromX(N+1, 1e18), dist_fromZ(N+1, 1e18);
    auto dijkstra = [&](ll start, vector<ll> &dist){
        priority_queue<pll, vector<pll>, greater<pll>> pq;
        dist[start] = 0;
        pq.push({0, start});
        while(!pq.empty()){
            auto [cd, cur] = pq.top(); pq.pop();
            if(cd > dist[cur]) continue;
            for(auto [nxt, w] : links[cur]){
                ll nd = cd + w;
                if(nd < dist[nxt]){
                    dist[nxt] = nd;
                    pq.push({nd, nxt});
                }
            }
        }
    };
    dijkstra(X, dist_fromX);
    dijkstra(Z, dist_fromZ);

    int P; cin >> P;
    vector<int> cand(P);
    rep(i, 0, P) cin >> cand[i];

    ll ans = 1e18;
    for(int c2: cand){
        vector<ll> dist_fromC(N+1, 1e18);
        dijkstra(c2, dist_fromC);
        for(int c1: cand) for(int c3: cand){
            if(c1 == c2 || c2 == c3 || c1 == c3) continue;
            ans = min(ans, dist_fromX[c1] + dist_fromC[c1] + dist_fromC[c3] + dist_fromZ[c3]);
        }
    }
    if(ans >= 1e18) ans = -1;
    cout << ans;
}